Linear-time recognition of bipartite graphs plus two edges (Q1868840)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Linear-time recognition of bipartite graphs plus two edges |
scientific article; zbMATH DE number 1901892
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Linear-time recognition of bipartite graphs plus two edges |
scientific article; zbMATH DE number 1901892 |
Statements
Linear-time recognition of bipartite graphs plus two edges (English)
0 references
28 April 2003
0 references
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.
0 references
graph algorithm
0 references
depth first search
0 references
parametric complexity
0 references
recognizing graph properties
0 references
max cut
0 references
linear-time algorithm
0 references
