CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Linear-time recognition of bipartite graphs plus two edges

Peter Damaschke (Institutionen för datavetenskap, Algoritmer)
Discrete Mathematics (0012-365X). Vol. 262 (2003), 1-3, p. 99-112.
[Artikel, refereegranskad vetenskaplig]

Cai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in linear time. We extend their result to bipartite graphs plus two edges. Our algorithm works on a depth-first-search spanning tree. This gives, as a byproduct, also a simplified solution to the one-edge case. It is a notoriously open question whether recognizing bipartite graphs plus $k$ edges is a fixed-parameter tractable problem. The present result might support the affirmative conjecture.

Nyckelord: algorithms and data structures, parametric complexity, recognizing graph properties, tree computations

Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.
CPL Pubid: 1848


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Algoritmer (2002-2004)


Information Technology

Chalmers infrastruktur