It is known that the problem of finding two disjoint paths such that the length of the longer path is minimized is strongly NP-hard, cf
Chung-Lun Li, S Thomas McCormick, and David Simchi-Levi. The complexity of finding two disjoint paths with min-max objective function. Discrete
Applied Mathematics, 26(1):105–115, 1990.
What about the spanning tree problem and the assignment problem?
Dear M.Poss,
i suggest to you a links and attached files in topics.
-Min-Max Results in Combinatorial Optimization
oai.cwi.nl/oai/asset/10149/10149D.pdf
-Discrete Optimization with Interval Data: Minmax Regret and Fuzzy ...
https://books.google.dz/books?isbn=3540784837
Best regards
Dear Michael,
Good morning.
I do not know. I'll try to get these answers.
Regards. Nelson
I don't think you really want to obtain all the answers. These are the interesting research questions. Here are few hints.
The assignment problem is polynomially solvable. The second best solution must be different from the best solution in at least one edge. Solve several assignement problems with the cost of the particular edge increased to exclude this edge from the solution. Select the second best solution.
I'm not completely right you mentioned the non-intersecting solutions, then I feel that the assignment problem is at least NP-hard.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms