Obtaining split graphs by edge contraction

DOI10.1016/j.tcs.2015.01.056zbMath1332.68075OpenAlexW2006468321MaRDI QIDQ897961

Leizhen Cai, Chengwei Guo

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.056

zbMATH Keywords

incompressibilitysplit graphsparameterized complexityFPT algorithmedge contraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75)

Related Items (5)

On the kernelization of split graph problems ⋮ Parameterized analysis and crossing minimization problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ An improved linear kernel for the cycle contraction problem ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Increasing the minimum degree of a graph by contractions
• A \(2k\) kernel for the cluster editing problem
• On problems without polynomial kernels
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Obtaining planarity by contracting few edges
• Contracting graphs to paths and trees
• A faster FPT algorithm for bipartite contraction
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Contracting Few Edges to Remove Forbidden Induced Subgraphs
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Faster Parameterized Algorithms for Deletion to Split Graphs
• Incompressibility through Colors and IDs
• Interval Deletion is Fixed-Parameter Tractable
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs

This page was built for publication: Obtaining split graphs by edge contraction