Golovach, P.A. and Kamiński, M. and Paulusma, Daniel and Thilikos, D.M. (2012) 'Induced packing of odd cycles in planar graphs.', Theoretical computer science., 420 . pp. 28-35.
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|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||February 2012|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|