受賞区分：国際学会・会議・シンポジウム等の賞  受賞国：台湾

Minimum joins in a graft $(G, T)$, also known as minimum $T$-joins of a graph $G$, are said to be connected if they determine a connected subgraph of $G$. Grafts with a connected minimum join have gained interest ever since Middendorf and Pfeiffer showed that they satisfy Seymour's min-max formula for joins and $T$-cut packings; that is, in such grafts, the size of a minimum join is equal to the size of a maximum packing of $T$-cuts. In this paper, we provide a constructive characterization of grafts with a connected minimum join. We also obtain a polynomial time algorithm that decides whether a given graft has a connected minimum join and, if so, outputs one. Our algorithm has two bottlenecks; one is the time required to compute a minimum join of a graft, and the other is the time required to solve the single-source all-sink shortest path problem in a graph with conservative $\pm 1$-valued edge weights. Thus, our algorithm runs in $O(n(m + n\log n) )$ time. In the nondense case, it improves upon the time bound for this problem due to Sebő and Tannier that was introduced as an application of their results on metrics on graphs.

arXiv

researchmap

その他リンク： https://arxiv.org/pdf/2510.26975v1

担当区分：筆頭著者,　責任著者   記述言語：英語   掲載種別：研究論文（大学，研究機関等紀要）  

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Journal of Graph Theory  

In matching theory, one of the most fundamental and classical branches of combinatorics, canonical decompositions of graphs are powerful and versatile tools that form the basis of this theory. However, the abilities of the known canonical decompositions, that is, the Dulmage–Mendelsohn, Kotzig–Lovász, and Gallai–Edmonds decompositions, are limited because they are only applicable to particular classes of graphs, such as bipartite graphs, or they are too sparse to provide sufficient information. To overcome these limitations, we introduce a new canonical decomposition that is applicable to all graphs and provides much finer information. This decomposition also provides the answer to the longstanding absence of a canonical decomposition that is nontrivially applicable to general graphs with perfect matchings. We focus on the notion of factor-components as the fundamental building blocks of a graph; through the factor-components, our new canonical decomposition states how a graph is organized and how it contains all the maximum matchings. The main results that constitute our new theory are the following: (i) a canonical partial order over the set of factor-components, which describes how a graph is constructed from its factor-components; (ii) a generalization of the Kotzig–Lovász decomposition, which shows the inner structure of each factor-component in the context of the entire graph; and (iii) a canonically described interrelationship between (i) and (ii), which integrates these two results into a unified theory of a canonical decomposition. These results are obtained in a self-contained way, and our proof of the generalized Kotzig–Lovász decomposition contains a shortened and self-contained proof of the classical counterpart.

DOI： 10.1002/jgt.23190

Open Access

Web of Science

Scopus

researchmap

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： https://doi.org/10.1016/j.dam.2022.08.024

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（大学，研究機関等紀要）  

開催年月日： 2025年12月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Victoria University of Wellington, Wellington   国名：ニュージーランド  

開催年月日： 2025年3月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Boca Raton, FL