TR-2002-04

A Gallai--Edmonds-type structure theorem for path-matchings.

Bianca Spille, László Szegő

Published in:
Journal of graph theory. 46 (2004) 93-102



Abstract

As a generalization of matchings, Cunningham and Geelen introduced the notion of path-matchings. We give a structure theorem for path-matchings which generalizes the fundamental Gallai-Edmonds structure theorem for matchings. Our proof is purely combinatorial.


Bibtex entry:

@techreport{egres-02-04,
AUTHOR = {Spille, Bianca and Szeg{\H o}, L{\'a}szl{\'o}},
TITLE = {A {G}allai--{E}dmonds-type structure theorem for path-matchings.},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-04}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!