Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs

DOI10.1007/978-3-540-77120-3_79zbMath1193.68194OpenAlexW2126383829MaRDI QIDQ5387826

Jiong Guo

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_79

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Two edge modification problems without polynomial kernels ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem ⋮ Obtaining split graphs by edge contraction ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Parameterized complexity of Eulerian deletion problems ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Quadratic vertex kernel for split vertex deletion ⋮ A polynomial kernel for trivially perfect editing ⋮ On the threshold of intractability ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ Incompressibility of \(H\)-free edge modification problems ⋮ Faster parameterized algorithms for deletion to split graphs ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph-modeled data clustering: Exact algorithms for clique generation
• Some complexity results about threshold graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A general method to speed up fixed-parameter-tractable algorithms
• Threshold graphs and related topics
• Parametrized complexity theory.
• NP-completeness results for edge modification problems
• Applying Modular Decomposition to Parameterized Bicluster Editing
• A More Effective Linear Kernelization for Cluster Editing
• Edge-Deletion Problems
• Graph Classes: A Survey
• Complexity classification of some edge modification problems

This page was built for publication: Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs