Length 3 Edge-Disjoint Paths Is NP-Hard
In 2003, it was claimed that the following problem was solvable in polynomial time: do there exist k edge-disjoint paths of length exactly 3 between vertices s and t in a given graph? The proof was flawed, and in this note we show that this problem is NP-hard. We use a reduction from Partial Orienta...
| Główni autorzy: | , |
|---|---|
| Kolejni autorzy: | |
| Format: | Artykuł |
| Język: | English |
| Wydane: |
SP Birkhäuser Verlag Basel
2017
|
| Dostęp online: | http://hdl.handle.net/1721.1/106920 https://orcid.org/0000-0001-5813-5029 |