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

DOI10.1007/978-3-540-77120-3_79MaRDI QIDQ5387826zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Quadratic vertex kernel for split vertex deletion
• Faster parameterized algorithms for deletion to split graphs
• Faster parameterized algorithms for deletion to split graphs
• Quadratic vertex kernel for split vertex deletion
• The complexity of some edge deletion problems

Cites work

• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A More Effective Linear Kernelization for Cluster Editing
• A general method to speed up fixed-parameter-tractable algorithms
• Applying Modular Decomposition to Parameterized Bicluster Editing
• Complexity classification of some edge modification problems
• Edge-Deletion Problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph Classes: A Survey
• Graph-modeled data clustering: Exact algorithms for clique generation
• Introduction to algorithms
• NP-completeness results for edge modification problems
• Parametrized complexity theory.
• Some complexity results about threshold graphs
• Threshold graphs and related topics

Cited in

(28)

• Kernel and fast algorithm for dense triplet inconsistency
• Polynomial kernels for proper interval completion and related problems
• Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
• Node-and edge-deletion NP-complete problems
• Polynomial kernels for edge modification problems towards block and strictly chordal graphs
• Edge deletion problems: branching facilitated by modular decomposition
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Two edge modification problems without polynomial kernels
• Parameterized complexity of Eulerian deletion problems
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• A cubic-vertex kernel for flip consensus tree
• A survey of parameterized algorithms and the complexity of edge modification
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Parameterized complexity of Eulerian deletion problems
• Quadratic vertex kernel for split vertex deletion
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Incompressibility of \(H\)-free edge modification problems
• Two edge modification problems without polynomial kernels
• Obtaining split graphs by edge contraction
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• Faster parameterized algorithms for deletion to split graphs
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Exploring the subexponential complexity of completion problems
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• Polynomial kernels for proper interval completion and related problems
• An improved kernelization algorithm for trivially perfect editing
• (Sub)linear kernels for edge modification problems toward structured graph classes
• Parameterized complexity of the \(\mathcal{T}_{h+1} \)-free edge deletion problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387826)