Contracting a chordal graph to a split graph or a tree

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

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, December). Contracting a chordal graph to a split graph or a tree. Presented at 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011, Warsaw, Poland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011
• Publication Date: Jan 1, 2011
• Deposit Date: Dec 6, 2011
• Print ISSN: 0302-9743
• 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