The complexity of finding two disjoint paths with min-max objective function (Q584275): Difference between revisions

The paper considers the problem of finding two disjoint paths from a given node s to another node t in a network such that the length of the longer path is minimized. The paths may be vertex-disjoint or arc- disjoint and the network may be directed or undirected. It is shown that all four versions as well as some related problems are strongly NP- complete. The paper also gives a pseudo-polynomial-time algorithm for the acyclic directed case.

0 references

reviewed by

Wai-Kai Chen

0 references

zbMATH Keywords

paths

0 references

vertex-disjoint

0 references

arc-disjoint

0 references

NP-complete

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

On the Complexity of Timetable and Multicommodity Flow Problems

0 references

The directed subgraph homeomorphism problem

0 references

Q4198056

0 references

Some simplified NP-complete graph problems

0 references

Parallel concepts in graph theory

0 references

The complexity of finding maximum disjoint paths with length constraints

0 references

Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph

0 references

Disjoint paths in a network

0 references

A quick method for finding shortest pairs of disjoint paths

0 references

full work available at URL

https://doi.org/10.1016/0166-218x(90)90024-7

0 references

Identifiers

zbMATH Open document ID

0693.05035

0 references

DOI

10.1016/0166-218X(90)90024-7

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:584275

@@ Property / author @@
-Chung-Lun Li
@@ Property / author: Chung-Lun Li / rank @@
-Normal rank
@@ Property / author @@
+Chung-Lun Li
@@ Property / author: Chung-Lun Li / rank @@
+Normal rank
@@ Property / review text @@
+The paper considers the problem of finding two disjoint paths from a given node s to another node t in a network such that the length of the longer path is minimized. The paths may be vertex-disjoint or arc- disjoint and the network may be directed or undirected. It is shown that all four versions as well as some related problems are strongly NP- complete. The paper also gives a pseudo-polynomial-time algorithm for the acyclic directed case.
+Normal rank
@@ Property / reviewed by @@
+Wai-Kai Chen
@@ Property / reviewed by: Wai-Kai Chen / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C38
@@ Property / Mathematics Subject Classification ID: 05C38 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C20
@@ Property / Mathematics Subject Classification ID: 05C20 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+4134076
@@ Property / zbMATH DE Number: 4134076 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+paths
@@ Property / zbMATH Keywords: paths / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+vertex-disjoint
@@ Property / zbMATH Keywords: vertex-disjoint / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+arc-disjoint
@@ Property / zbMATH Keywords: arc-disjoint / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+NP-complete
@@ Property / zbMATH Keywords: NP-complete / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+On the Complexity of Timetable and Multicommodity Flow Problems
+Normal rank
@@ Property / cites work @@
+The directed subgraph homeomorphism problem
@@ Property / cites work: The directed subgraph homeomorphism problem / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Some simplified NP-complete graph problems
@@ Property / cites work: Some simplified NP-complete graph problems / rank @@
+Normal rank
@@ Property / cites work @@
+Parallel concepts in graph theory
@@ Property / cites work: Parallel concepts in graph theory / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of finding maximum disjoint paths with length constraints
+Normal rank
@@ Property / cites work @@
+Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
+Normal rank
@@ Property / cites work @@
+Disjoint paths in a network
@@ Property / cites work: Disjoint paths in a network / rank @@
+Normal rank
@@ Property / cites work @@
+A quick method for finding shortest pairs of disjoint paths
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0166-218x(90)90024-7
+Normal rank
@@ Property / OpenAlex ID @@
+W2019637647
@@ Property / OpenAlex ID: W2019637647 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:584275