論文

本文へのリンクあり
2021年5月24日

Constructive Characterization of Critical Bipartite Grafts

  • Nanao Kita

Factor-critical graphs are a classical concept in matching theory that
constitute an important component of the Gallai-Edmonds canonical decomposition
and Edmonds' algorithm for maximum matchings. Lovász provided a constructive
characterization of factor-critical graphs in terms of ear decompositions. This
characterization has been a useful inductive tool for studying factor-critical
graphs and also connects them with Edmonds' algorithm.
Joins in grafts, also known as $T$-joins in graphs, are a classical variant
of matchings proposed in terms of parity. Minimum joins and grafts are
generalizations of perfect matchings and graphs with perfect matchings,
respectively. Accordingly, graft analogues of fundamental concepts and results
from matching theory, such as canonical decompositions, will develop the theory
of minimum join. In this paper, we propose a new concept, critical quasicombs,
as a bipartite graft analogue of factor-critical graphs and provide a
constructive characterization of critical quasicombs using a graft version of
ear decompositions. This characterization can be considered as a bipartite
graft analogue of Lovász' result. From our results, the Dulmage-Mendelsohn
canonical decomposition, originally a theory for bipartite graphs, has been
generalized for bipartite grafts.

リンク情報
arXiv
http://arxiv.org/abs/arXiv:2105.11167
URL
http://arxiv.org/abs/2105.11167v1
URL
http://arxiv.org/pdf/2105.11167v1 本文へのリンクあり
ID情報
  • arXiv ID : arXiv:2105.11167

エクスポート
BibTeX RIS