Edge-disjoint paths in expander graphs

No abstract is available for this paper.

• Publication year

  2000

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2000-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/S0097539700366103
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Splitting an Expander Graph

  1999cited by this paper
• Disjoint Paths in Expander Graphs via Random Walks: A Short Survey

  1998cited by this paper
• Multicommodity flow and circuit switching

  1998cited by this paper
• Large Deviation Bounds for Markov Chains

  1997cited by this paper
• Short paths in expander graphs

  1996cited by this paper
• Graph Minors .XIII. The Disjoint Paths Problem

  1995cited by this paper
• Circuit Switching: a Multicommodity Ow Based Approach

  1995cited by this paper
• Optimal construction of edge-disjoint paths in random graphs

  1994cited by this paper
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs

  1994influential reference
• A Chernoff bound for random walks on expander graphs

  1993cited by this paper
• Existence and construction of edge disjoint paths on expander graphs

  1992cited by this paper
• Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

  1987cited by this paper
• Constructing disjoint paths on expander graphs

  1987cited by this paper
• On approximate counting

  1982cited by this paper
• Graph Theory with Applications

  1977influential reference
• Ramanujan Graphs

  1965influential reference
• A theorem on flows in networks

  1957influential reference

• New Structures and Algorithms for Length-Constrained Expander Decompositions

  2024cites this paper
• Blockchain-based Transaction Group Key Management Scheme For Edge Devices

  2023cites this paper
• Edge-disjoint paths in expanders: online with removals

  2023cites this paper
• Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

  2023cites this paper
• Sublinear Algorithms for Hierarchical Clustering

  2022cites this paper
• Large Minors in Expanders

  2019cites this paper
• Ramanujan graphs and the spectral gap of supercomputing topologies

  2019cites this paper
• Waypoint Routing in Special Networks

  2018cites this paper
• Network-Design Problems in Graphs and on the Plane

  2018cites this paper
• Charting the Complexity Landscape of Waypoint Routing

  2017cites this paper
• Distributed MST and Routing in Almost Mixing Time

  2017cites this paper
• Almost polynomial hardness of node-disjoint paths in grids

  2017cites this paper
• Extension Complexity of Independent Set Polytopes

  2016influential citation
• Disjoint Paths and Unsplittable Flow ( Version 2 . 7 )

  2016cites this paper
• Sparsifying Congested Cliques and Core-Periphery Networks

  2016cites this paper
• New algorithms for maximum disjoint paths based on tree-likeness

  2016cites this paper
• Unconditional Lower Bounds in Complexity Theory

  2015cites this paper
• Algorithmic complexity: Between Structure and Knowledge How Pursuit-evasion Games help. (Complexité algorithmique: entre structure et connaissance. Comment les jeux de poursuite peuvent apporter des solutions)

  2014cites this paper
• Final Reading Project : Polylogarithmic Approximation Algorithn for Routing with Constant Congestion

  2014cites this paper
• Approximation Algorithms for Network Routing and Facility Location Problems

  2014cites this paper
• Communication lower bounds via critical block sensitivity

  2013cites this paper
• Probabilistic Spectral Sparsification In Sublinear Time

  2013cites this paper
• Approximation algorithms for submodular optimization and graph problems

  2013cites this paper
• Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion

  2013cites this paper
• Braess's paradox in expanders

  2012cites this paper
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

  2012cites this paper
• Routing in undirected graphs with constant congestion

  2011cites this paper
• Locating a target with an agent guided by unreliable local advice: how to beat the random walk when you have a clock?

  2010cites this paper
• Disjoint paths in sparse graphs

  2009cites this paper
• A logarithmic approximation for unsplittable flow on line graphs

  2009cites this paper
• The fractional congestion bound for efficient edge disjoint routing

  2008influential citation
• Random Walks on Random Graphs

  2008cites this paper
• Improving Search in Unstructured Peer-to-Peer Systems

  2008cites this paper
• DISJOINT PATHS IN SPARSE GRAPHS

  2008cites this paper
• Edge-Disjoint Paths and Unsplittable Flow

  2007cites this paper
• Polylogarithmic Independence Can Fool DNF Formulas

  2007influential citation
• Finding Disjoint Paths in Expanders Deterministically and Online

  2007influential citation
• Improving Search Using a Fault-Tolerant Overlay in Unstructured P2P Systems

  2007cites this paper
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow

  2006cites this paper
• An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing

  2006influential citation
• Adversarial Reasoning: Computational Approaches to Reading the Opponent's Mind

  2006influential citation
• EDGE DISJOINT PATHS AND MULTICUT PROBLEMS IN GRAPHS GENERALIZING THE TREES

  2005cites this paper
• Constructing Efficient and Fault-Tolerant Unstructured Peer-To-Peer Networks

  2005influential citation
• Efficient lookup on unstructured topologies

  2005cites this paper
• Approximation Algorithms for the Unsplittable Flow Problem ∗

  2005influential citation
• AN ALGORITHMIC FRIEDMAN–PIPPENGER THEOREM ON TREE EMBEDDINGS (PRELIMINARY VERSION)

  2004cites this paper
• Subpath protection for scalability and fast recovery in optical WDM mesh networks

  2004cites this paper
• Approximation Algorithms for the Unsplittable Flow Problem

  2002influential citation
• Corrigendum: Edge-Disjoint Paths in Expander Graphs

  2002cites this paper
• Mixing time and long paths in graphs

  2002cites this paper
• New algorithmic aspects of the Local Lemma with applications to routing and partitioning

  2002cites this paper
• Arc-disjoint paths in expander digraphs

  2001cites this paper