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)

Ämnesområden

Information Technology

Chalmers infrastruktur