[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

E. Eiben, R. Ganian, S. Szeider:
"Solving Problems on Graphs of High Rank-Width";
Vortrag: Algorithms and Data Structures Symposium, Victoria, Canada; 05.08.2015 - 07.08.2015; in: "Proceedings of the 14th International Symposium on Algorithms and Data Structures", LNCS, 9214 (2015), ISBN: 978-3-319-21839-7; S. 314 - 326.



Kurzfassung englisch:
A modulator of a graph G to a specified graph class H is a set
of vertices whose deletion puts G into H. The cardinality of a modulator
to various graph classes has long been used as a structural parameter
which can be exploited to obtain FPT algorithms for a range of hard
problems. Here we investigate what happens when a graph contains a
modulator which is large but "well-structured" (in the sense of having
bounded rank-width). Can such modulators still be exploited to obtain
efficient algorithms? And is it even possible to find such modulators
efficiently?
We first show that the parameters derived from such well-structured
modulators are strictly more general than the cardinality of modulators
and rank-width itself. Then, we develop an FPT algorithm for finding
such well-structured modulators to any graph class which can be characterized
by a finite set of forbidden induced subgraphs. We proceed by
showing how well-structured modulators can be used to obtain efficient
parameterized algorithms for Minimum Vertex Cover and Maximum
Clique. Finally, we use the concept of well-structured modulators to
develop an algorithmic meta-theorem for efficiently deciding problems
expressible in Monadic Second Order (MSO) logic, and prove that this
result is tight in the sense that it cannot be generalized to LinEMSO
problems.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_247934.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.