Minimizing the stabbing number of matchings, trees, and triangulations

DOI10.1007/S00454-008-9114-6MaRDI QIDQ1006396zbMATH OpenOpenAlexFDO

Authors Sándor P. Fekete, Marco E. Lübbecke, Henk 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

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

Recommendations

• scientific article; zbMATH DE number 6469175
• Integer programming approaches for minimum stabbing problems
• The minimum stabbing triangulation problem: IP models and computational evaluation
• Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons
• Finding stabbing lines in 3-space

Cites work

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

Cited in

(7)

• scientific article; zbMATH DE number 6469175 (Why is no real title available?)
• Rectangularization of digital objects and its relation with straight skeletons
• The minimum stabbing triangulation problem: IP models and computational evaluation
• Partitions of rectilinear polygons with minimum stabbing number
• Minimizing the stabbing number of matchings, trees, and triangulations
• Computing conforming partitions of orthogonal polygons with minimum stabbing number
• Minimum stabbing rectangular partitions of rectilinear polygons

Describes a project that uses

Uses Software

• TSPLIB

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1006396)