Obtaining split graphs by edge contraction

DOI10.1016/J.TCS.2015.01.056MaRDI QIDQ897961zbMATH OpenOpenAlexFDO

Authors Chengwei Guo, Leizhen Cai

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

incompressibilityFPT algorithmparameterized complexityedge contractionsplit graphs

Mathematics Subject Classification ID

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

Recommendations

• Obtaining split graphs by edge contraction
• scientific article; zbMATH DE number 6862097
• Split contraction: the untold story
• On the parameterized approximability of contraction to classes of chordal graphs
• Contraction Blockers for Graphs with Forbidden Induced Paths

Cites work

• scientific article; zbMATH DE number 2080275 (Why is no real title available?)
• A \(2k\) kernel for the cluster editing problem
• Contracting few edges to remove forbidden induced subgraphs
• Faster parameterized algorithms for deletion to split graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Incompressibility through Colors and IDs
• Increasing the minimum degree of a graph by contractions
• Interval deletion is fixed-parameter tractable
• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• On problems without polynomial kernels
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs

Cited in

(9)

• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• An improved linear kernel for the cycle contraction problem
• Containment relations in split graphs
• Split contraction: the untold story
• Obtaining split graphs by edge contraction
• On the kernelization of split graph problems
• A survey of parameterized algorithms and the complexity of edge modification
• On the parameterized approximability of contraction to classes of chordal graphs
• Parameterized analysis and crossing minimization problems

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

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