On Ear Decompositions of Strongly Connected Bidirected Graphs

Simple item page
dc.creatorBabenko, Maxim A.
dc.date2006-09-08
dc.date.accessioned2026-07-07T07:24:38Z
dc.date.available2026-07-07T07:24:38Z
dc.descriptionBidirected graphs (earlier studied by Edmonds, Johnson and, in equivalent terms of skew-symmetric graphs, by Tutte, Goldberg, Karzanov, and others) proved to be a useful unifying language for describing both flow and matching problems. In this paper we extend the notion of ear decomposition to the class of strongly connected bidirected graphs. In particular, our results imply Two Ear Theorem on matching covered graphs of Lovász and Plummer. The proofs given here are self-contained except for standard Barrier Theorem on skew-symmetric graphs.
dc.description16 pages, 5 figures
dc.identifierhttps://arxiv.org/abs/math/0609221
dc.identifierhttp://arxiv.org/abs/math/0609221
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/116433
dc.subjectCombinatorics
dc.subject05C38, 05C40, 05C75
dc.titleOn Ear Decompositions of Strongly Connected Bidirected Graphs
dc.typetext

Files

Collections

arXiv