Generalized vertex covering in interval graphs
type: Item
instance of: scholarly article
title: Generalized vertex covering in interval graphs
zbMATH Open document ID: 0766.05082
DOI: 10.1016/0166-218X(92)90116-R
author: Madhav V. Marathe
author: R. Ravi
author: C. Pandu Rangan
published in: Discrete Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: The following decision problem is treated in the paper: Given a graph \(G\) and two integers \(i\geq 2\), \(k\geq 1\), is it possible to find \(k\) vertices of the graph such that any complete subgraph of \(G\) with \(i\) vertices contains (at least) one of these distinguished vertices. This problem is NP-complete even for chordal graphs. In this paper a greedy linear-time algorithm for interval graphs is presented --- in fact the algorithm solves the corresponding optimization problem. In particular the minimum vertex cover problem \((i=2)\) and the minimum feedback vertex set problem \((i=3)\) can be solved in linear time for interval graphs.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 94341
zbMATH Keywords: greedy linear-time algorithm
zbMATH Keywords: interval graphs
zbMATH Keywords: vertex cover
reviewed by: Erich Prisner
MaRDI profile type: Publication
cites work: On finding the minimum bandwidth of interval graphs
cites work: The complexity of generalized clique covering
cites work: Q3328583
cites work: Finding Hamiltonian circuits in interval graphs
cites work: A unified approach to domination problems on interval graphs
cites work: Linear algorithm for domatic number problem on interval graphs
full work available at URL: 0166-218x(92)90116-r
OpenAlex ID: W2041800134
description: scientific article; zbMATH DE number 94341