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).
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.
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
Export: | |
Look up in GoogleScholar |