P. A. Golovach
Contracting a chordal graph to a split graph or a tree
Golovach, P. A. ; Kaminski, M.; Paulusma, D.
Authors
Contributors
F. Murlak
Editor
P. Sankowski
Editor
Abstract
The problems Contractibility and Induced Minor are to test whether a graph G contains a graph H as a contraction or as an induced minor, respectively. We show that these two problems can be solved in |VG|f(|VH|)VGf(VH) time if G is a chordal input graph and H is a split graph or a tree. In contrast, we show that containment relations extending Subgraph Isomorphism can be solved in linear time if G is a chordal input graph and H is an arbitrary graph not part of the input.
Citation
Golovach, P. A., Kaminski, M., & Paulusma, D. (2011). Contracting a chordal graph to a split graph or a tree. In F. Murlak, & P. Sankowski (Eds.), Mathematical Foundations of Computer Science 2011, 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011 ; proceedings (339-350). https://doi.org/10.1007/978-3-642-22993-0_32
Conference Name | 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011 |
---|---|
Conference Location | Warsaw, Poland |
Publication Date | Jan 1, 2011 |
Deposit Date | Dec 6, 2011 |
Pages | 339-350 |
Series Title | Lecture notes in computer science |
Series Number | 6907 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Mathematical Foundations of Computer Science 2011, 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011 ; proceedings. |
ISBN | 9783642229923 |
DOI | https://doi.org/10.1007/978-3-642-22993-0_32 |
Public URL | https://durham-repository.worktribe.com/output/1157649 |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search