A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911622693388288 |
|---|---|
| author | Kano, Takumi Yamaguchi, Yutaro |
| author_facet | Kano, Takumi Yamaguchi, Yutaro |
| contents | We present a deterministic linear-time algorithm for finding an odd cycle through two specified vertices in an undirected graph. This is shown in a generalized form as follows: Let $Γ$ be any group in which every element is of order at most $2$. For a given $Γ$-labeled graph with two specified vertices (or edges), we can determine in linear time whether there exist two cycles with distinct labels that are through both of the two specified vertices (or edges), and find such cycles if yes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23169 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices Kano, Takumi Yamaguchi, Yutaro Data Structures and Algorithms Combinatorics We present a deterministic linear-time algorithm for finding an odd cycle through two specified vertices in an undirected graph. This is shown in a generalized form as follows: Let $Γ$ be any group in which every element is of order at most $2$. For a given $Γ$-labeled graph with two specified vertices (or edges), we can determine in linear time whether there exist two cycles with distinct labels that are through both of the two specified vertices (or edges), and find such cycles if yes. |
| title | A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2604.23169 |