Scholarlink

We present an algorithm for finding a perfect matching in a 3-edge-connected cubic graph that intersects every 3-edge cut in exactly one edge. Specifically, we propose an algorithm with a time complexity of \(O(n \log ^4 n)\) , which significantly improves upon the previously known \(O(n^3)\) -time algorithms for the same problem. The technique we use for the improvement is efficient use of the cactus model of 3-edge cuts. As an application, we use our algorithm to compute embeddings of 3-edge-connected cubic graphs with limited number of singular edges (i.e., edges that are twice in the boundary of one face) in \(O(n \log ^4 n)\) time; this application contributes to the study of the well-known Cycle Double Cover conjecture.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the Time Complexity of Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Babak Ghanbari,
  • Robert Šámal

摘要

We present an algorithm for finding a perfect matching in a 3-edge-connected cubic graph that intersects every 3-edge cut in exactly one edge. Specifically, we propose an algorithm with a time complexity of \(O(n \log ^4 n)\) , which significantly improves upon the previously known \(O(n^3)\) -time algorithms for the same problem. The technique we use for the improvement is efficient use of the cactus model of 3-edge cuts. As an application, we use our algorithm to compute embeddings of 3-edge-connected cubic graphs with limited number of singular edges (i.e., edges that are twice in the boundary of one face) in \(O(n \log ^4 n)\) time; this application contributes to the study of the well-known Cycle Double Cover conjecture.