Guyslain Naves
Congestion in planar graphs with demands on faces.
Tue, 08/24/2010 - 15:01 — SomNambulAuthors: Guyslain Naves, Christophe Weibel
Subjects: Discrete Mathematics
AbstractWe give an algorithm to route a multicommodity flow in a planar graph $G$
with congestion $O(\log k)$, where $k$ is the maximum number of terminals on
the boundary of a face, when each demand edge lie on a face of $G$. We also
show that our specific method cannot achieve a substantially better congestion.On disjoint paths in acyclic planar graphs.
Tue, 08/24/2010 - 15:01 — SomNambulAuthors: Guyslain Naves
Subjects: Discrete Mathematics
AbstractWe give an algorithm with complexity $O(f(R)^{k^2} k^3 n)$ for the integer
multiflow problem on instances $(G,H,r,c)$ with $G$ an acyclic planar digraph
and $r+c$ Eulerian. Here, $f$ is a polynomial function, $n = |V(G)|$, $k =
|E(H)|$ and $R$ is the maximum request $\max_{h \in E(H)} r(h)$. When $k$ is
fixed, this gives a polynomial algorithm for the arc-disjoint paths problem
under the same hypothesis.The hardness of routing two pairs on one face.
Tue, 11/17/2009 - 16:01 — SomNambulAuthors: Guyslain Naves
Subjects: Discrete Mathematics
AbstractWe prove the NP-completeness of the integer multiflow problem in planar
graphs, with the following restrictions: there are only two demand edges, both
lying on the infinite face of the routing graph. This was one of the open
challenges concerning disjoint paths, explicitly asked by M\"uller. It also
strengthens Schw\"arzler's recent proof of one of the open problems of
Schrijver's book, about the complexity of the edge-disjoint paths problem with
terminals on the outer boundary of a planar graph. We also give a directed
acyclic reduction.
User login
