EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses

Archontia C. Giannopoulou, Sebastian Wiederrecht

Combinatorica · 2026-06 · 46 (3)

DOI: 10.1007/s00493-026-00211-4 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Combinatorica, online erschienen am 04.05.2026. Verfasst von Archontia C. Giannopoulou und 1 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Korea Advanced Institute of Science and Technology.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B . A conformal cross over some cycle C is a pair of disjoint paths $$P_1$$ P 1 , $$P_2$$ P 2 which are internally disjoint from C , the endpoints of each path separate the endpoints of the other path on C , and both $$C\cup P_1\cup P_2$$ C ∪ P 1 ∪ P 2 and $$B-(V(C)\cup V(P_1)\cup V(P_2))$$ B - ( V ( C ) ∪ V ( P 1 ) ∪ V ( P 2 ) ) have a perfect matching. We show that if C is a 4-cycle in a brace B , then C has a a conformal cross if and only if B contains $$K_{3,3}$$ K 3 , 3 as a matching minor. This result implies a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.

Förderung

  • Korea Advanced Institute of Science and Technology

Zitieren

APA

Giannopoulou, A. C., & Wiederrecht, S. (2026). Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses. Combinatorica, 46(3). https://doi.org/10.1007/s00493-026-00211-4

Vancouver

Giannopoulou AC, Wiederrecht S. Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses. Combinatorica. 2026;46(3). doi:10.1007/s00493-026-00211-4

BibTeX
@article{Giannopoulou2026,
  author = {Giannopoulou, Archontia C. and Wiederrecht, Sebastian},
  title = {Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses},
  journal = {Combinatorica},
  year = {2026},
  volume = {46},
  number = {3},
  doi = {10.1007/s00493-026-00211-4}
}
Kostenlos starten →