A Bottleneck Matching Problem with Edge-Crossing Constraints

DOI10.1142/S0218195915500144zbMath1358.90112OpenAlexW2289848075MaRDI QIDQ2792796

John Gunnar Carlsson, Haritha Bellam, Saladi Rahul, Benjamin Armbruster

Publication date: 14 March 2016

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195915500144

zbMATH Keywords

dynamic programmingmatchingsbottleneckapproximation algorithmsnon-crossing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (11)

New variants of perfect non-crossing matchings ⋮ Faster bottleneck non-crossing matchings of points in convex position ⋮ Parameterized analysis and crossing minimization problems ⋮ Approximating the bottleneck plane perfect matching of a point set ⋮ New variants of perfect non-crossing matchings ⋮ Structural properties of bichromatic non-crossing matchings ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ Connecting the dots (with minimum crossings) ⋮ Flip distance to some plane configurations ⋮ Flip Distance to some Plane Configurations. ⋮ Monochromatic plane matchings in bicolored point set

Cites Work

• Reconstructing sets of orthogonal line segments in the plane
• The complexity of detecting crossingfree configurations in the plane
• On a matching problem in the plane
• Bottleneck Non-crossing Matching in the Plane
• An adaptive forecasting algorithm and inventory policy for products with short life cycles
• Crane scheduling with non-crossing constraint
• Planar Formulae and Their Uses
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas

This page was built for publication: A Bottleneck Matching Problem with Edge-Crossing Constraints