Article

Short length menger's theorem and reliable optical routing

Authors:

Amitabha Bagchi,

Amitabh Chaudhary,

Petr KolmanAuthors Info & Claims

SPAA '03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures

Pages 246 - 247

https://doi.org/10.1145/777412.777453

Published: 07 June 2003 Publication History

Get Access

Abstract

We deal with a generalization of the Minimum path colouring problem, k-Edge disjoint path systems colouring: given a graph G and a set of pairs of vertices of G, the task is to connect each pair by a system of k-edge disjoint paths (a k-system) and to colour the k-systems by minimal number of colours in such way that any two edge-intersecting k-systems have different colours. Multiple connecting paths between the same pair of vertices are motivated by a need for fault tolerant connections. We propose an O(k² F) approximation algorithm for this problem where F is the flow number of the graph. As a byproduct of our analysis we also show that any two k-connected vertices in G are connected by k edge disjoint paths of average length O(k F) which improves previously known bounds for many classes of graphs.

References

[1]

A. Bagchi, A. Chaudhary, P. Kolman, and C. Scheideler. Algorithms for fault-tolerant routing in circuit switched networks. In SPAA '02, pages 265--274, 2002.

Digital Library

Google Scholar

[2]

V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. In STOC '99, pages 19--28, 1999.

Digital Library

Google Scholar

[3]

P. Kolman and C. Scheideler. Improved bounds for the unsplittable flow problem. In SODA '02, pages 184--193, 2002.

Digital Library

Google Scholar

[4]

Y. Rabani. Path coloring on the mesh. In FOCS '96, pages 400--409, 1996.

Digital Library

Google Scholar

[5]

C. Scheideler. Probabilistic Methods for Coordination Problems. Habilitation thesis, University of Paderborn, July 2000.

Google Scholar

Cited By

View all

Chuzhoy JMakarychev YVijayaraghavan AZhou Y(2015)Approximation Algorithms and Hardness of the k-Route Cut ProblemACM Transactions on Algorithms (TALG)10.1145/264481412:1(1-40)Online publication date: 31-Dec-2015
https://dl.acm.org/doi/10.1145/2644814
Koch RSkutella MSpenke I(2007)Maximum k-Splittable s,t-FlowsTheory of Computing Systems10.1007/s00224-007-9068-843:1(56-66)Online publication date: 1-Dec-2007
https://doi.org/10.1007/s00224-007-9068-8
Bagchi AChaudhary AGoodrich MXu S(2003)Constructing Disjoint Paths for Secure CommunicationDistributed Computing10.1007/978-3-540-39989-6_13(181-195)Online publication date: 2003
https://doi.org/10.1007/978-3-540-39989-6_13

Index Terms

Short length menger's theorem and reliable optical routing
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
      2. Paths and connectivity problems
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
    2. Graph algorithms analysis
      1. Network flows

Recommendations

Short length Menger's theorem and reliable optical routing

In the minimun path coloring problem, we are given a graph and a set of pairs of vertices of the graph and we are asked to connect the pairs by colored paths in such a way that paths of the same color are edge disjoint. In this paper we deal with a ...
Algorithms for Fault-Tolerant Routing in Circuit-Switched Networks

In this paper we consider the $k$ edge-disjoint paths problem ($k$-EDP), a generalization of the well-known edge-disjoint paths problem. Given a graph $G=(V,E)$ and a set of terminal pairs (or requests) $T$, the problem is to find a maximum subset of ...
Algorithms for fault-tolerant routing in circuit switched networks
SPAA '02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures

In this paper we consider the k edge-disjoint paths problem (k-EDP), a generalization of the well-known edge-disjoint paths problem. Given a graph G=(V,E) and a set of terminal pairs (or requests) T, the problem is to find a maximum subset of the pairs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures

June 2003

374 pages

ISBN:1581136617

DOI:10.1145/777412

General Chair:
Arnold Rosenberg
University of Massachusetts
,
Program Chair:
Friedhelm Meyer auf der Heide
U. Paderborn

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA03

Sponsor:

SPAA03: 15th ACM Symposium on Parallelism in Algorithms and Architecturesn

June 7 - 9, 2003

California, San Diego, USA

Acceptance Rates

SPAA '03 Paper Acceptance Rate 38 of 106 submissions, 36%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
264
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chuzhoy JMakarychev YVijayaraghavan AZhou Y(2015)Approximation Algorithms and Hardness of the k-Route Cut ProblemACM Transactions on Algorithms (TALG)10.1145/264481412:1(1-40)Online publication date: 31-Dec-2015
https://dl.acm.org/doi/10.1145/2644814
Koch RSkutella MSpenke I(2007)Maximum k-Splittable s,t-FlowsTheory of Computing Systems10.1007/s00224-007-9068-843:1(56-66)Online publication date: 1-Dec-2007
https://doi.org/10.1007/s00224-007-9068-8
Bagchi AChaudhary AGoodrich MXu S(2003)Constructing Disjoint Paths for Secure CommunicationDistributed Computing10.1007/978-3-540-39989-6_13(181-195)Online publication date: 2003
https://doi.org/10.1007/978-3-540-39989-6_13

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Short length Menger's theorem and reliable optical routing

Algorithms for Fault-Tolerant Routing in Circuit-Switched Networks

Algorithms for fault-tolerant routing in circuit switched networks