Academic Journal
Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
| العنوان: | Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree |
|---|---|
| المؤلفون: | Bulian, J, Dawar, A |
| بيانات النشر: | Springer Science and Business Media LLC //dx.doi.org/10.1007/s00453-015-0045-3 Algorithmica |
| سنة النشر: | 2016 |
| المجموعة: | Apollo - University of Cambridge Repository |
| مصطلحات موضوعية: | Graph, Isomorphism, Canonization, Parameterized complexity, Fixed-parameter tractable, Bounded degree, Graph theory, Complexity theory, Tree-depth |
| الوصف: | A commonly studied means of parameterizing graph problems is the deletion distance from triviality [11], which counts vertices that need to be deleted from a graph to place it in some class for which e cient algorithms are known. In the context of graph isomorphism, we de ne triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is FPT when parameterized by elimination distance to bounded degree, extending results of Bouland et al. ; The work was supported in part by EPSRC grant EP/H026835, DAAD grant A/13/05456, and DFG project Logik, Struktur und das Graphenisomorphieproblem. ; This is the final version of the article. It first appeared from Springer via http://dx.doi.org/10.1007/s00453-015-0045-3 |
| نوع الوثيقة: | article in journal/newspaper |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | https://www.repository.cam.ac.uk/handle/1810/249190 |
| الاتاحة: | https://www.repository.cam.ac.uk/handle/1810/249190 |
| Rights: | Creative Commons Attribution 4.0 ; http://creativecommons.org/licenses/by/4.0/ |
| رقم الانضمام: | edsbas.48ED52F8 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |