✦ LIBER ✦

On the complexity of the edge-disjoint min–min problem in planar digraphs

✍ Scribed by Longkun Guo; Hong Shen

Book ID: 113927619
Publisher: Elsevier Science
Year: 2012
Tongue: English
Weight: 342 KB
Volume: 432
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2011.12.009

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the complexity of the planar directed

On the complexity of the planar directed edge-disjoint paths problem

✍ Dirk Müller 📂 Article 📅 2005 🏛 Springer-Verlag 🌐 English ⚖ 278 KB

On the complexity of the planar edge-dis

On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary

✍ Werner Schwärzler 📂 Article 📅 2009 🏛 Springer-Verlag 🌐 English ⚖ 363 KB

On the Solution of Min-sum-min Problems

✍ Alexei Demyanov 📂 Article 📅 2005 🏛 Springer US 🌐 English ⚖ 136 KB

The complexity of finding two disjoint p

The complexity of finding two disjoint paths with min-max objective function

✍ Chung-Lun Li; S.Thomas McCormick; David Simchi-Levi 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 689 KB

Complexity of the min–max (regret) versi

Complexity of the min–max (regret) versions of min cut problems

✍ Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Complexity of the min–max and min–max re

Complexity of the min–max and min–max regret assignment problems

✍ Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 179 KB

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment pro