Graph separators: a parameterized view
| Autor: | Henning Fernau, Jochen Alber, Rolf Niedermeier |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Discrete mathematics
Computer Networks and Communications Applied Mathematics Voltage graph Strength of a graph Butterfly graph Divide-and-conquer algorithms Theoretical Computer Science law.invention Planar graph Parameterized complexity Graph separator theorems symbols.namesake Computational Theory and Mathematics law Line graph Fixed parameter tractability Graph minor symbols Graph (abstract data type) Planar graph problems Null graph Algorithm Mathematics |
| Zdroj: | Journal of Computer and System Sciences. 67:808-832 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/s0022-0000(03)00072-2 |
| Popis: | Graph separation is a well-known tool to make (hard) graph problems accessible to a divide-and-conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way to easily check whether a planar graph problem will allow for a fixed parameter algorithm of running time cknO(1) for constant c. One of the main contributions of the paper is to exactly compute the base c of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant c. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect