Monday, 14:15 - 14:40 h, Room: H 3005


Serguei Norine
Pairs of disjoint cycles

Coauthors: Robin Thomas, Hein van der Holst


We will describe a polynomial-time algorithm which determines whether an input graph contains a pair of disjoint cycles with the given property. In particular, it allows one to test whether a graph has two disjoint odd cycles, whether it has two disjoint cycles, one non-zero modulo 3 and the other non-zero modulo 5, whether a graph embedded in a surface has two disjoint homologically non-trivial cycles, and whether a given embedding of a graph in 3-space is linkless.
The algorithm is based on an efficient characterization of the span of a certain collection of matrices indexed by pairs of disjoint cycles, extending a theorem of van der Holst and a characterization of linklessly embeddable graphs due to Robertson, Seymour and Thomas.


Talk 3 of the invited session Mon.2.H 3005
"Structural graph theory and methods" [...]
Cluster 2
"Combinatorial optimization" [...]


  payday loans direct . Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.