Finding Short Cycles in an Embedded Graph in Polynomial Time
| dc.creator | Ren, Han | |
| dc.creator | Cao, Ni | |
| dc.date | 2008-07-10 | |
| dc.date.accessioned | 2026-07-07T09:49:34Z | |
| dc.date.available | 2026-07-07T09:49:34Z | |
| dc.description | Let ${\cal{C}}_1$ be the set of fundamental cycles of breadth-first-search trees in a graph $G$ and ${\cal{C}}_2$ the set of the sums of two cycles in ${\cal{C}}_1$. Then we show that $(1) {\cal{C}}={\cal{C}}_1\bigcup{\cal{C}}_2$ contains a shortest $Π$-twosided cycle in a $Π$-embedded graph $G$;$(2)$ $\cal{C}$ contains all the possible shortest even cycles in a graph $G$;$(3)$ If a shortest cycle in a graph $G$ is an odd cycle, then $\cal{C}$ contains all the shortest odd cycles in $G$. This implies the existence of a polynomially bounded algorithm to find a shortest $Π-$twosided cycle in an embedded graph and thus solves an open problem of B.Mohar and C.Thomassen[2,pp112] | |
| dc.identifier | https://arxiv.org/abs/0807.1620 | |
| dc.identifier | http://arxiv.org/abs/0807.1620 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/164638 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C10, 05C30 | |
| dc.title | Finding Short Cycles in an Embedded Graph in Polynomial Time | |
| dc.type | text |