Approximation algorithms for edge-disjoint paths and unsplittable flow

被引：0
|
作者：
Erlebach, T [1 ]
机构：
[1] Univ Leicester, Dept Comp Sci, Leicester, Leics, England
来源：
EFFICIENT APPROXIMATION AND ONLINE ALGORITHMS: RECENT PROGRESS ON CLASSICAL COMBINATORIAL OPTIMIZATION PROBLEMS AND NEW APPLICATIONS | 2006年 / 3484卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In the maximum edge-disjoint paths problem (MEDP) the input consists of a graph and a set of requests (pairs of vertices), and the goal is to connect as many requests as possible along edge-disjoint paths. We give a survey of known results about the complexity and approximability of MEDP and sketch some of the main ideas that have been used to obtain approximation algorithms for the problem. We consider also the generalization of MEDP where the edges of the graph have capacities and each request has a profit and a demand, called the unsplittable flow problem.
引用
收藏
页码：97 / 134
页数：38
相关论文
共 50 条
  • [1] Approximation algorithms for edge-disjoint paths and unsplittable flow
    Department of Computer Science, University of Leicester, United Kingdom
    Lect. Notes Comput. Sci., 2006, (97-134):
  • [2] Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems
    Srinivasan, A
    38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, : 416 - 425
  • [3] Approximation Algorithms for the Edge-Disjoint Paths Problem via Racke Decompositions
    Andrews, Matthew
    2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, : 277 - 286
  • [4] AN APPROXIMATION ALGORITHM FOR FULLY PLANAR EDGE-DISJOINT PATHS
    Huang, Chien-Chung
    Mari, Mathieu
    Mathieu, Claire
    Schewior, Kevin
    Vygen, Jens
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) : 752 - 769
  • [5] Exact Algorithms for Finding Partial Edge-Disjoint Paths
    Deng, Yunyun
    Guo, Longkun
    Huang, Peihuang
    COMPUTING AND COMBINATORICS (COCOON 2018), 2018, 10976 : 14 - 25
  • [6] Reconstructing edge-disjoint paths
    Conforti, M
    Hassin, R
    Ravi, R
    OPERATIONS RESEARCH LETTERS, 2003, 31 (04) : 273 - 276
  • [7] A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
    Chuzhoy, Julia
    Li, Shi
    JOURNAL OF THE ACM, 2016, 63 (05)
  • [8] A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
    Chuzhoy, Julia
    Li, Shi
    2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2012, : 233 - 242
  • [9] Edge-Disjoint Paths Revisited
    Chekuri, Chandra
    Khanna, Sanjeev
    ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)
  • [10] On-line algorithms for edge-disjoint paths in trees of rings
    Anand, RS
    Erlebach, T
    LATIN 2002: THEORETICAL INFORMATICS, 2002, 2286 : 584 - 597
12345