Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
A Note on n-Critical Bipartite Graphs and Its Application
verfasst von : Yueping Li, Zhe Nie
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In matching theory,
n
-critical graphs play an important role in the decomposition of graphs with respect to perfect matchings. Since bipartite graphs cannot be
n
-critical when
n
> 0, we amend the classical definition of
n
-critical graphs and propose the concept of
n
-critical bipartite graphs. Let
G
= (
B
,
W
;
E
) be a bipartite graph with
n
= |
W
| − |
B
|, where
B
and
W
are the bipartitions of vertex set,
E
is the edge set. Then,
G
is
n
-critical if when deleting any
n
distinct vertices of
W
, the remaining subgraph of
G
has a perfect matching. Furthermore, an algorithm for determining
n
-critical bipartite graphs is given which runs in
O
(|
W
||
E
|) time, in the worst case. Our work helps to design a job assignment circuit which has high robustness.