Solving geometric covering problems by data reduction

DOI10.1007/978-3-540-30140-0_67MaRDI QIDQ5464633zbMATH OpenOpenAlexFDO

Authors Steffen Mecke, Dorothea Wagner

Publication date 18 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100428

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Station location -- complexity and approximation
• Set covering with almost consecutive ones property
• THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
• Red-blue covering problems and the consecutive ones property
• Locating stops along bus or railway lines -- a bicriteria problem

Cited in

(12)

• Red-blue covering problems and the consecutive ones property
• Set covering with almost consecutive ones property
• Tree decompositions of graphs: saving memory in dynamic programming
• Station location -- complexity and approximation
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• Benders decomposition for set covering problems. Almost satisfying the consecutive ones property
• Understanding the effectiveness of data reduction in public transportation networks
• A faster algorithm for finding minimum Tucker submatrices
• Stop location design in public transportation networks: covering and accessibility objectives
• Exact algorithms and applications for tree-like Weighted Set Cover
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

This page was built for publication: Solving geometric covering problems by data reduction

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