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

DOI10.1016/j.ipl.2010.07.010zbMath1234.05224OpenAlexW1999116155MaRDI QIDQ407573

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

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 setcovering problemconsecutive ones property

Mathematics Subject Classification ID

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

Related Items (1)

Exact algorithms and hardness results for geometric red-blue hitting set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• 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
• PC trees and circular-ones arrangements.
• Incidence matrices and interval graphs
• A threshold of ln n for approximating set cover
• Wavelength rerouting in optical networks, or the Venetian Routing problem

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