|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
A matching M in a graph G is a subset of the edges of G such that each vertex of G is hit by at most one edge of M. A connected matching is a matching M such that EVERY pair of edges of M is joined by an edge of G. Plummer, Steibitz and Toft introduced connected matchings in connection with their work on Hadwiger's Conjecture. An induced matching in a graph G is a matching M such that NO pair of edges of M is joined by an edge of G; that is, an induced matching is a matching which forms an induced subgraph of G. As is typical in the field of graph algorithms, we show these problems to be hard in certain classes and easy in others. Hosts: Jørgen Bang-Jensen and Bjarne Toft
SDU HOME | IMADA HOME | Previous Page Last modified: August 15, 2003. Joan Boyar (joan@imada.sdu.dk) |