Obtaining a Bipartite Graph by Contracting Few Edges
From MaRDI portal
Publication:5408613
DOI10.1137/130907392zbMath1285.05167OpenAlexW2165648442MaRDI QIDQ5408613
Christophe Paul, Daniel Lokshtanov, Pim van 't Hof, Pinar Heggernes
Publication date: 10 April 2014
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3357/
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (22)
Paths to Trees and Cacti ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Graph editing to a fixed target ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ MSOL restricted contractibility to planar graphs ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ An improved linear kernel for the cycle contraction problem ⋮ Unnamed Item ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Reducing graph transversals via edge contractions ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
This page was built for publication: Obtaining a Bipartite Graph by Contracting Few Edges
