Talks and Poster Presentations (with Proceedings-Entry):
F. Fomin, S. Gaspers, P. Golovach, K. Suchan, St. Szeider, E. van Leeuwen, M. Vatshelle, Y. Villanger:
"k-Gap Interval Graphs";
Talk: Latin American Theoretical Informatics Symposium,
Arequipa, Peru;
2012-04-16
- 2012-04-20; in: "Proceedings of the 10th Latin American Theoretical Informatics Symposium (LATIN 2012)",
D. Fernández-Baca (ed.);
Lecture Notes in Computer Science / Springer,
7256
(2012),
ISBN: 978-3-642-29343-6;
350
- 361.
English abstract:
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k -gap interval graph if it has a multiple interval representation with at most n + k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k = 0), we parameterize graph problems by k , and find FPT algorithms for several problems, including Feedback Vertex Set , Dominating Set , Independent Set , Clique , Clique Cover , and Multiple Interval Transversal . The Coloring problem turns out to be -hard and we design an XP algorithm for the recognition problem.
Keywords:
Computer Science
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-29344-3_30
Related Projects:
Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Created from the Publication Database of the Vienna University of Technology.