Obtaining split graphs by edge contraction

DOI10.1016/J.TCS.2015.01.056zbMATH Open1332.68075OpenAlexW2006468321MaRDI QIDQ897961FDOQ897961

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

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

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)

Cites Work

• Fixed-parameter tractability of graph modification problems for hereditary properties
• A \(2k\) kernel for the cluster editing problem
• On problems without polynomial kernels
• Incompressibility through Colors and IDs
• Obtaining planarity by contracting few edges
• Increasing the minimum degree of a graph by contractions
• Obtaining a bipartite graph by contracting few edges
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Title not available (Why is that?)
• 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
• Interval deletion is fixed-parameter tractable

Cited In (9)

• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• An improved linear kernel for the cycle contraction problem
• Split contraction: the untold story
• Containment relations in split graphs
• 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)