[图书][B] Graph factors and matching extensions
QR Yu, G Liu - 2010 - cds.cern.ch
Abstract Graph Factors and Matching Extensions deals with two important branches of graph
theory-factor theory and extendable graphs. Due to the mature techniques and wide ranges …
theory-factor theory and extendable graphs. Due to the mature techniques and wide ranges …
Finding all maximally-matchable edges in a bipartite graph
T Tassa - Theoretical Computer Science, 2012 - Elsevier
We consider the problem of finding all maximally-matchable edges in a bipartite graph G=(V,
E), ie, all edges that are included in some maximum matching. We show that given any …
E), ie, all edges that are included in some maximum matching. We show that given any …
A partially ordered structure and a generalization of the canonical partition for general graphs with perfect matchings
N Kita - … : 23rd International Symposium, ISAAC 2012, Taipei …, 2012 - Springer
This paper is concerned with structures of general graphs with perfect matchings. We first
reveal a partially ordered structure among elementary components of general graphs with …
reveal a partially ordered structure among elementary components of general graphs with …
Robust assignments via ear decompositions and randomized rounding
D Adjiashvili, V Bindewald, D Michaels - arXiv preprint arXiv:1607.02437, 2016 - arxiv.org
Many real-life planning problems require making a priori decisions before all parameters of
the problem have been revealed. An important special case of such problem arises in …
the problem have been revealed. An important special case of such problem arises in …
Computing the forcing spectrum of outerplanar graphs in polynomial time
M Gorsky, F Kreßin - arXiv preprint arXiv:2401.17704, 2024 - arxiv.org
The forcing number of a graph with a perfect matching $ M $ is the minimum number of
edges in $ M $ whose endpoints need to be deleted, such that the remaining graph only has …
edges in $ M $ whose endpoints need to be deleted, such that the remaining graph only has …
Disclosing barriers: a generalization of the canonical partition based on Lovász's formulation
N Kita - International Conference on Combinatorial …, 2013 - Springer
Given a graph, a barrier is a set of vertices determined by the Berge formula—the min-max
theorem characterizing the size of maximum matchings. The notion of barriers plays …
theorem characterizing the size of maximum matchings. The notion of barriers plays …
A canonical characterization of the family of barriers in general graphs
N Kita - arXiv preprint arXiv:1212.5960, 2012 - arxiv.org
Given a graph, a barrier is a set of vertices determined by the Berge formula---the min-max
theorem characterizing the size of maximum matchings. The notion of barriers plays …
theorem characterizing the size of maximum matchings. The notion of barriers plays …
[HTML][HTML] Ear decomposition and induced even cycles
D Peng, X Wang - Discrete Applied Mathematics, 2019 - Elsevier
Lovász shows that a matching covered graph G has an ear decomposition starting with an
arbitrary edge of G. A 2-edge-connected cubic graph is matching covered. Using Oum's …
arbitrary edge of G. A 2-edge-connected cubic graph is matching covered. Using Oum's …
An alternative proof of Lovász's cathedral theorem
N Kita - Journal of the Operations Research Society of Japan, 2014 - jstage.jst.go.jp
A graph G with a perfect matching iscalled saturated ifC+ e has more perfect matchings than
a forany edge e that isnot in C. LovEsz gave a cliaracterization of the saturated graphs …
a forany edge e that isnot in C. LovEsz gave a cliaracterization of the saturated graphs …
New canonical decomposition in matching theory
N Kita - arXiv preprint arXiv:1708.01051, 2017 - arxiv.org
In matching theory, one of the most fundamental and classical branches of
combinatorics,{\em canonical decompositions} of graphs are powerful and versatile tools …
combinatorics,{\em canonical decompositions} of graphs are powerful and versatile tools …