Golovach, P.A. and Kaminski, M. and Paulusma, Daniel and Thilikos, D.M. (2012) 'Induced packing of odd cycles in planar graphs.', Theoretical computer science. .
An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of k odd cycles in an n-vertex graph can be found (if it exists) in time 2O(k3/2)⋅n2+ϵ (for any constant ϵ>0) when the input graph is planar. We also show that deciding if a graph has an induced packing of two odd induced cycles is NP-complete.
|Keywords:||Planar graphs, Induced packing, Odd cycles, Irrelevant vertex technique, Fixed parameter tractability.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1016/j.tcs.2011.11.004|
|Record Created:||07 Dec 2011 15:20|
|Last Modified:||03 Apr 2013 16:21|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|