Increasing the Minimum Degree of a Graph by Contractions
From MaRDI portal
Publication:2891338
DOI10.1007/978-3-642-28050-4_6zbMath1352.68106MaRDI QIDQ2891338
Daniël Paulusma, Petr A. Golovach, Marcin Kaminski, Dimitrios M. Thilikos
Publication date: 15 June 2012
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/10711/1/10711.pdf
68Q25: Analysis of algorithms and problem complexity
05C12: Distance in graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- 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
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Edge Contractions in Subclasses of Chordal Graphs
- Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
- 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
- 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
