Increasing the minimum degree of a graph by contractions

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

zbMATH Keywords

degree contractibility problemweighted degree contractibility problem

Mathematics Subject Classification ID

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