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|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2011|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|