Efficient labelling algorithms for the maximum noncrossing matching problem

Efficient labelling algorithms for the maximum noncrossing matching problem

0.00 Avg rating0 Votes
Article ID: iaor1995282
Country: Netherlands
Volume: 47
Issue: 2
Start Page Number: 175
End Page Number: 179
Publication Date: Nov 1993
Journal: Discrete Applied Mathematics
Authors: , ,
Keywords: combinatorial analysis
Abstract:

Consider a bipartite graph; let’s suppose the origin nodes and the destination nodes are drawn, arranged in two columns, and the edges as straight-line segments. A noncrossing matching is a subset of edges such that no two of them intersect. Several algorithms for the problem of finding the noncrossing matching of maximum cardinality are proposed. Moreover an extension to weighted graphs is considered.

Reviews

Required fields are marked *. Your email address will not be published.