Increasing the minimum degree of a graph by contractions
From MaRDI portal
Publication:385061
DOI10.1016/j.tcs.2013.02.030zbMath1296.05185OpenAlexW2063166459MaRDI QIDQ385061
Petr A. Golovach, Daniël Paulusma, Dimitrios M. Thilikos, Marcin Kaminski
Publication date: 29 November 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/10711/1/10711.pdf
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)
Related Items (10)
On the parameterized complexity of maximum degree contraction problem ⋮ Graph editing to a fixed target ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ Obtaining split graphs by edge contraction ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ An improved linear kernel for the cycle contraction problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of finding small degree-constrained subgraphs
- On graph contractions and induced minors
- Edge-contraction problems
- On the parameterized complexity of multiple-interval graph problems
- Partitioning graphs into connected parts
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- On the NP-hardness of edge-deletion and -contraction problems
- Contracting graphs to paths and trees
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Finding small separators in linear time via treewidth reduction
- The Complexity Status of Problems Related to Sparsest Cuts
- Edge Contractions in Subclasses of Chordal Graphs
- Searching for a Visible, Lazy Fugitive
- Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
- Finding Large Clique Minors is Hard
- The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
- Contractions of Planar Graphs in Polynomial Time
- The computational complexity of graph contractions II: Two tough polynomially solvable cases
- Contractibility and NP-completeness
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Contraction and Treewidth Lower Bounds
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Contracting chordal graphs and bipartite graphs to paths and trees
This page was built for publication: Increasing the minimum degree of a graph by contractions
