Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
F. Fomin, S. Gaspers, P. Golovach, K. Suchan, St. Szeider, E. van Leeuwen, M. Vatshelle, Y. Villanger:
"k-Gap Interval Graphs";
Vortrag: Latin American Theoretical Informatics Symposium,
Arequipa, Peru;
16.04.2012
- 20.04.2012; in: "Proceedings of the 10th Latin American Theoretical Informatics Symposium (LATIN 2012)",
D. Fernández-Baca (Hrg.);
Lecture Notes in Computer Science / Springer,
7256
(2012),
ISBN: 978-3-642-29343-6;
S. 350
- 361.
Kurzfassung englisch:
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.
Schlagworte:
Computer Science
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-29344-3_30
Zugeordnete Projekte:
Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.