Red-blue covering problems and the consecutive ones property

DOI10.1016/J.JDA.2007.11.002zbMATH Open1161.90018OpenAlexW2159264028MaRDI QIDQ1018089FDOQ1018089

Authors: Michael Dom, Jiong Guo, Rolf Niedermeier, Sebastian Wernicke 

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

Recommendations

• Publication:4952637
• Set covering with almost consecutive ones property
• An improved algorithm for the red-blue hitting set problem with the consecutive ones property
• Minimum Membership Set Covering and the Consecutive Ones Property
• On the minimum degree hypergraph problem with subset size two and the red-blue set cover problem with the consecutive ones property

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)

Cites Work

• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• A new polynomial-time algorithm for linear programming
• Introduction to algorithms
• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Parametrized complexity theory.
• Title not available (Why is that?)
• Structure preserving reductions among convex optimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for the set covering problem
• Title not available (Why is that?)
• Optimal Capacity Scheduling—I
• Orthogonal segment stabbing
• PC trees and circular-ones arrangements.
• Title not available (Why is that?)
• Wavelength rerouting in optical networks, or the Venetian Routing problem
• A structure theorem for the consecutive 1's property
• On the consecutive ones property
• Set covering with almost consecutive ones property
• Station location -- complexity and approximation
• Algorithms – ESA 2004
• The consecutive ones submatrix problem for sparse matrices
• Computing and Combinatorics
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems

Cited In (12)

• Red blue set cover problem on axis-parallel hyperplanes and other objects
• The bus rapid transit investment problem
• 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
• Set covering with almost consecutive ones property
• On the minimum degree hypergraph problem with subset size two and the red-blue set cover problem with the consecutive ones property
• Title not available (Why is that?)
• Minimum membership covering and hitting
• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• Minimum Membership Set Covering and the Consecutive Ones Property
• Algorithms – ESA 2004
• Geometric red-blue set cover for unit squares and related problems

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

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