Golovach, P.A. and Kaminski, M. and Paulusma, Daniel (2011) 'Contracting a chordal graph to a split graph or a tree.', in Mathematical Foundations of Computer Science 2011, 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011 ; proceedings. Berlin: Springer, pp. 339-350. Lecture notes in computer science. (6907).
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.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-22993-0_32|
|Record Created:||13 Dec 2011 11:50|
|Last Modified:||03 Apr 2013 16:23|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|