Generalized vertex covering in interval graphs

DOI10.1016/0166-218X(92)90116-RzbMath0766.05082OpenAlexW2041800134MaRDI QIDQ1199467

R. Ravi, C. Pandu Rangan, Madhav V. Marathe

Publication date: 16 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90116-r

zbMATH Keywords

interval graphsvertex covergreedy linear-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

A linear-time algorithm for the weighted feedback vertex problem on interval graphs ⋮ Maximum \(h\)-colourable subgraph problem in balanced graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Complexity of maximum cut on interval graphs

Cites Work

• Unnamed Item
• Finding Hamiltonian circuits in interval graphs
• A unified approach to domination problems on interval graphs
• On finding the minimum bandwidth of interval graphs
• The complexity of generalized clique covering
• Linear algorithm for domatic number problem on interval graphs

This page was built for publication: Generalized vertex covering in interval graphs