Finding Short Cycles in an Embedded Graph in Polynomial Time

Details Finding Short Cycles in an Embedded Graph in Polynomial Time Finding Short Cycles in an Embedded Graph in Polynomial Time

2008-07-10

arxiv.org/abs/0807.1620v1

Mathematics

Combinatorics

Scientific paper

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 $\Pi$-twosided cycle in a $\Pi$-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 $\Pi-$twosided cycle in an embedded graph and thus solves an open problem of B.Mohar and C.Thomassen[2,pp112]

Affiliated with

Also associated with

No associations

Rating

Finding Short Cycles in an Embedded Graph in Polynomial Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Short Cycles in an Embedded Graph in Polynomial Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Short Cycles in an Embedded Graph in Polynomial Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-459561