Linear-time recognition of bipartite graphs plus two edges

DOI10.1016/S0012-365X(02)00493-4MaRDI QIDQ1868840zbMATH OpenOpenAlexFDO

Authors Peter Damaschke

Publication date 28 April 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00493-4

zbMATH Keywords

depth first searchgraph algorithmlinear-time algorithmmax cutparametric complexityrecognizing graph properties

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Review text

This paper marks a second step towards a fixed parameter algorithm for MAX CUT. The first step was done by \textit{L. Cai} and \textit{B. Schieber} [Discrete Appl. Math. 73, 27-34 (1997; Zbl 0867.05066)] who proved that bipartite graphs plus one edge can be recognized in linear time. Several edge deletion problems like feed-back arc set are fixed parameter tractable due to the general Robertson-Seymour theory. This does not apply here since bipartite graphs are not closed under edge contraction.

Recommendations

• Edge Bipartization Faster Than 2ᵏ
• Linear-Time Approximation Algorithms for the Max Cut Problem
• scientific article; zbMATH DE number 2084262
• Edge bipartization faster than \(2^k\)
• Planar graph bipartization in linear time

Cited in

(3)

• The recognition problem for line bigraphs
• Linear-time recognition of double-threshold graphs
• Kempe equivalence of almost bipartite graphs

This page was built for publication: Linear-time recognition of bipartite graphs plus two edges

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