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

DOI10.1016/J.IPL.2010.07.010zbMATH Open1234.05224OpenAlexW1999116155MaRDI QIDQ407573FDOQ407573

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

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

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)

Cites Work

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

Cited In (2)

• Red blue set cover problem on axis-parallel hyperplanes and other objects
• Exact algorithms and hardness results for geometric red-blue hitting set problem

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)