Anzeige
Erschienen in:
2024 | OriginalPaper | Buchkapitel
Characterizations of Bricks and Braces
verfasst von : Cláudio L. Lucchesi, U. S. R. Murty
Erschienen in: Perfect Matchings
Verlag: Springer Nature Switzerland
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
Recall that a matching covered graph which is free of nontrivial tight cuts is a brace if it is bipartite, and is a brick if it is nonbipartite. In Chapter 4 we presented a proof of Lovász’s Uniqueness Theorem (4.17) for tight cut decompositions, which is one of the cornerstones of this theory. According to that theorem, every matching covered graph has a unique decomposition into bricks and braces (up to multiple edges). The proof of this fundamental result simply relied on the fact that bricks and braces are free of nontrivial tight cuts. But this fact by itself is inadequate to suggest efficient procedures for recognizing these basic objects. In this chapter, we address these issues by establishing characterizations of bricks and braces which lead to polynomial-time recognition algorithms.We deal with bricks in this section and braces in Section 5.4.