Obtaining split graphs by edge contraction
From MaRDI portal
Publication:897961
DOI10.1016/j.tcs.2015.01.056zbMath1332.68075OpenAlexW2006468321MaRDI QIDQ897961
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
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
