Obtaining a bipartite graph by contracting few edges

DOI10.1137/130907392MaRDI QIDQ5408613zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Pim Van 't Hof, Daniel Lokshtanov, Christophe Paul

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/

zbMATH Keywords

bipartite graphsedge contractionsfixed-parameter tractabilitygraph modification problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• Edge Bipartization Faster Than 2ᵏ

Cited in

(28)

• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Paths to trees and cacti
• On the parameterized complexity of contraction to generalization of trees
• Reducing graph transversals via edge contractions
• Complexity and algorithms for constant diameter augmentation problems
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• An improved linear kernel for the cycle contraction problem
• On the parameterized complexity of grid contraction
• A single exponential-time FPT algorithm for cactus contraction
• Obtaining a bipartite graph by contracting few edges
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Graph editing to a fixed target
• Smaller kernels for several FPT problems based on simple observations
• Parameterized complexity of three edge contraction problems with degree constraints
• Reducing graph transversals via edge contractions
• MSOL restricted contractibility to planar graphs
• Paths to trees and cacti
• Contracting to a longest path in H-free graphs
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• Reducing the vertex cover number via edge contractions
• A survey of parameterized algorithms and the complexity of edge modification
• Vertex identification to a forest
• Parameterized complexity of biclique contraction and balanced biclique contraction
• On the complexity of establishing hereditary graph properties via vertex splitting
• The parameterized landscape of labeled graph contractions
• A finer view of the parameterized landscape of labeled graph contractions
• On the parameterized complexity of maximum degree contraction problem

This page was built for publication: Obtaining a bipartite graph by contracting few edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408613)