Red-blue covering problems and the consecutive ones property

DOI10.1016/j.jda.2007.11.002zbMath1161.90018OpenAlexW2159264028MaRDI QIDQ1018089

Rolf Niedermeier, Sebastian Wernicke, Michael Dom, Jiong Guo

Publication date: 13 May 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.11.002

zbMATH Keywords

NP-completenessset coverhitting setminimum degree hypergraphminimum membership set cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (4)

Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ An improved algorithm for the red-blue hitting set problem with the consecutive ones property ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Minimum membership covering and hitting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orthogonal segment stabbing
• A new polynomial-time algorithm for linear programming
• Structure preserving reductions among convex optimization problems
• Optimization, approximation, and complexity classes
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On the consecutive ones property
• PC trees and circular-ones arrangements.
• Set covering with almost consecutive ones property
• Parametrized complexity theory.
• A structure theorem for the consecutive 1's property
• The consecutive ones submatrix problem for sparse matrices
• Station Location - Complexity and Approximation.
• A threshold of ln n for approximating set cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Optimal Capacity Scheduling—I
• Wavelength rerouting in optical networks, or the Venetian Routing problem
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
• Algorithms – ESA 2004
• Computing and Combinatorics
• Algorithms for the set covering problem

This page was built for publication: Red-blue covering problems and the consecutive ones property