Advertisement
Published in:
2007 | OriginalPaper | Chapter
Linear Problem Kernels for NP-Hard Problems on Planar Graphs
Authors : Jiong Guo, Rolf Niedermeier
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We develop a generic framework for deriving linear-size problem kernels for NP-hard problems on planar graphs. We demonstrate the usefulness of our framework in several concrete case studies, giving new kernelization results for
Connected Vertex Cover
,
Minimum Edge Dominating Set
,
Maximum Triangle Packing
, and
Efficient Dominating Set
on planar graphs. On the route to these results, we present effective, problem-specific data reduction rules that are useful in any approach attacking the computational intractability of these problems.