Minimizing the stabbing number of matchings, trees, and triangulations

DOI10.1007/s00454-008-9114-6zbMath1167.90628OpenAlexW3137400503MaRDI QIDQ1006396

Sándor P. Fekete, Marco E. Lübbecke, Henk G. Meijer

Publication date: 24 March 2009

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9114-6

zbMATH Keywords

MatchingComplexityTriangulationSpanning treeIterated roundingLinear programming relaxationStabbing number

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (5)

Partitions of rectilinear polygons with minimum stabbing number ⋮ Minimum stabbing rectangular partitions of rectilinear polygons ⋮ Computing conforming partitions of orthogonal polygons with minimum stabbing number ⋮ Rectangularization of digital objects and its relation with straight skeletons ⋮ Minimizing the stabbing number of matchings, trees, and triangulations

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stabbing Delaunay tetrahedralizations
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Minimizing the stabbing number of matchings, trees, and triangulations
• Geometric algorithms and combinatorial optimization
• Approximating minimum-weight triangulations in three dimensions
• Rectilinear decompositions with low stabbing number
• Cost-driven octree construction schemes: An experimental study
• Quasi-optimal range searching in spaces of finite VC-dimension
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On simple polygonalizations with optimal area
• Spanning trees with low crossing number
• Odd Minimum Cut-Sets and b-Matchings
• Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• Algorithms and Data Structures
• Optimal Covering Tours with Turn Costs
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Minimizing the stabbing number of matchings, trees, and triangulations