An improved algorithm for the red-blue hitting set problem with the consecutive ones property

DOI10.1016/J.IPL.2010.07.010MaRDI QIDQ407573zbMATH OpenOpenAlexFDO

Authors Maw-Shang Chang, Hsiao-Han Chung, Chuang-Chieh Lin

Publication date 27 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.07.010

zbMATH Keywords

shortest pathdesign of algorithmshitting setconsecutive ones propertycovering problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Recommendations

• Exact algorithms and hardness results for geometric red-blue hitting set problem
• Red-blue covering problems and the consecutive ones property
• An exact algorithm for connected red-blue dominating set
• An exact algorithm for connected red-blue dominating set
• A randomised approximation algorithm for the hitting set problem
• A randomised approximation algorithm for the hitting set problem
• On the minimum degree hypergraph problem with subset size two and the red-blue set cover problem with the consecutive ones property
• A variant of Reiter's hitting-set algorithm
• Approximation algorithms in the successive hitting set model
• Algorithms for implicit hitting set problems

Cites work

• scientific article; zbMATH DE number 1445322 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• A note on two problems in connexion with graphs
• A threshold of ln n for approximating set cover
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• Incidence matrices and interval graphs
• Introduction to algorithms
• PC trees and circular-ones arrangements.
• Red-blue covering problems and the consecutive ones property
• Structure preserving reductions among convex optimization problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Wavelength rerouting in optical networks, or the Venetian Routing problem

Cited in

(5)

• Red blue set cover problem on axis-parallel hyperplanes and other objects
• Red-blue covering problems and the consecutive ones property
• Exact algorithms and hardness results for geometric red-blue hitting set problem
• A linear-time algorithm for the minimum degree hypergraph problem with 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

This page was built for publication: An improved algorithm for the red-blue hitting set problem with the consecutive ones property

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