Efficient labelling algorithms for the maximum noncrossing matching problem

DOI10.1016/0166-218X(93)90090-BzbMath0789.68113MaRDI QIDQ1315996

Daniele Pretolani, Thomas Ottmann, Federico Malucelli

Publication date: 17 March 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graphpermutationVLSI layoutlongest increasing subsequencenoncrossing matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (6)

Strongly stable and maximum weakly stable noncrossing matchings ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ Constrained tree inclusion ⋮ Optimal partition of a bipartite graph into non-crossing matchings ⋮ Optimal Partition of a Bipartite Graph with Prescribed Layout into Non-Crossing b-Matchings ⋮ Computing maximum non-crossing matching in convex bipartite graphs

Cites Work

• Unnamed Item
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• Priority Search Trees

This page was built for publication: Efficient labelling algorithms for the maximum noncrossing matching problem