An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing

No abstract is available for this paper.

• Publication year

  2006

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2006-01-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1109557.1109672
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An algorithmic Friedman{Pippenger theorem on tree embeddings and applications

  2008cited by this paper
• Embedding nearly-spanning bounded degree trees

  2007influential reference
• Better lossless condensers through derandomized curve samplers

  2006cited by this paper
• Iterative Construction of Cayley Expander Graphs

  2006cited by this paper
• New algorithmic aspects of the Local Lemma with applications to routing and partitioning

  2002influential reference
• Randomness conductors and constant-degree lossless expanders

  2002cited by this paper
• Corrigendum: Edge-Disjoint Paths in Expander Graphs

  2002influential reference
• Loss-less condensers, unbalanced expanders, and extractors

  2001cited by this paper
• Arc-disjoint paths in expander digraphs

  2001influential reference
• Graph Colouring and the Probabilistic Method

  2001cited by this paper
• Edge-disjoint paths in expander graphs

  2000influential reference
• On Defect Sets in Bipartite Graphs (Extended Abstract)

  1997cited by this paper
• On extracting randomness from weak random sources (extended abstract)

  1996cited by this paper
• Efficient routing in optical networks

  1996influential reference
• The size-Ramsey number of trees

  1995cited by this paper
• Computing with very weak random sources

  1994cited by this paper
• Efficient routing and scheduling algorithms for optical networks

  1994cited by this paper
• Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications

  1993influential reference
• Network Flows: Theory, Algorithms, and Applications

  1993cited by this paper
• On-line algorithms for path selection in a nonblocking network

  1990cited by this paper
• A lower bound on strictly non-blocking networks

  1988cited by this paper
• Wide-Sense Nonblocking Networks

  1988influential reference
• Expanding graphs contain all small trees

  1987influential reference
• Constructing disjoint paths on expander graphs

  1987cited by this paper
• Non-blocking networks

  1986influential reference
• On size Ramsey number of paths, trees, and circuits. I

  1983cited by this paper
• Rearrangeable Networks with Limited Depth

  1982influential reference
• The Complexity of Testing Whether a Graph is a Superconcentrator

  1981cited by this paper
• Hamiltonian circuits in random graphs

  1976influential reference
• Proceedings of Symposia in Applied Mathematics.

  1961cited by this paper

• Universality of random graphs

  2008cites this paper
• An algorithmic Friedman{Pippenger theorem on tree embeddings and applications

  2008cites this paper
• Defect Set Problem

  2007cites this paper
• Valiant Load Balancing, Capacity Provisioning and Resilient Backbone Design

  2007cites this paper