Skip to main content

Research Repository

Advanced Search

Contracting a chordal graph to a split graph or a tree

Golovach, P. A. ; Kaminski, M.; Paulusma, D.

Authors

P. A. Golovach

M. Kaminski



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



Downloadable Citations