### Abstract

We describe an algorithm, which for fixed k ≥ 0 has running time O(|V(G)|^{3}), to solve the following problem: given a graph G and k pairs of vertices of G, decide if there are k mutually vertex-disjoint paths of G joining the pairs.

Original language | English (US) |
---|---|

Pages (from-to) | 65-110 |

Number of pages | 46 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 63 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1995 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Graph minors .XIII. The disjoint paths problem'. Together they form a unique fingerprint.

## Cite this

Robertson, N., & Seymour, P. D. (1995). Graph minors .XIII. The disjoint paths problem.

*Journal of Combinatorial Theory, Series B*,*63*(1), 65-110. https://doi.org/10.1006/jctb.1995.1006