On disjoint paths in acyclic planar graphs

Details On disjoint paths in acyclic planar graphs On disjoint paths in acyclic planar graphs

2010-08-21

arxiv.org/abs/1008.3652v1

Computer Science

Discrete Mathematics

Scientific paper

We 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.

Affiliated with

Also associated with

No associations

Rating

On disjoint paths in acyclic planar graphs 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 On disjoint paths in acyclic planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On disjoint paths in acyclic planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-189052