NDLI: Sparse spanners vs. compact routing

Please wait, while we are loading the content...

Graph expansion and communication costs of fast matrix multiplication: regular submission

A study of transactional memory vs. locks in practice

Filtering: a method for solving graph problems in MapReduce

Brief announcement: full reversal routing as a linear dynamical system

A tight runtime bound for synchronous gathering of autonomous robots with limited visibility

Approximation algorithms for secondary spectrum auctions

Online packet-routing in grids with bounded buffers

Brief announcement: distributed shared memory based on computation migration

On a local protocol for concurrent file transfers

Brief announcement: a partitioned ticket lock

Tight bounds for anonymous adopt-commit objects

Scheduling irregular parallel computations on hierarchical caches

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Optimizing hybrid transactional memory: the importance of nonspeculative operations

Parallelism and data movement characterization of contemporary application classes

Brief announcement: better speedups for parallel max-flow

Stabilizing consensus with the power of two choices

Maximising lifetime for fault-tolerant target coverage in sensor networks

Sparse spanners vs. compact routing

Brief announcement: communication bounds for heterogeneous architectures

On multi-processor speed scaling with migration: extended abstract

Brief announcement: transaction polymorphism

A highly-efficient wait-free universal construction

Sharing-aware algorithms for virtual machine colocation

Linear-work greedy parallel approximate set cover and variants

Flat-combining NUMA locks

Work-stealing for mixed-mode parallelism by deterministic team-building

Brief announcement: reclaiming the energy of a schedule, models and algorithms

Convergence of local communication chain strategies via linear transformations: or how to trade locality for speed

Convergence to equilibrium of logit dynamics for strategic games

Re-Chord: a self-stabilizing chord overlay network

Brief announcement: large-scale multimaps

On scheduling in map-reduce and flow-shops

Brief announcement: multilane - a concurrent blocking multiset

A lock-free algorithm for concurrent bags

Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data

Parallelism in dynamic well-spaced point sets

Location-based memory fences

The pochoir stencil compiler

Brief announcement: paging for multicore processors

The car sharing problem

On a bounded budget network creation game

Recommender systems with non-binary grades

Brief announcement: processor allocation for optimistic parallelization of irregular programs

Finding heavy distinct hitters in data streams

Brief announcement: read invisibility, virtual world consistency and permissiveness are compatible

Understanding bloom filter intersection for lazy address-set disambiguation

Brief announcement: locality-enhancing loop transformations for tree traversal algorithms

Brief announcement: program regularization in verifying memory consistency

Brief announcement: RedRem: a parallel redundancy remover

Sparse spanners vs. compact routing

Content Provider	ACM Digital Library
Author	Gavoille, Cyril Sommer, Christian
Abstract	Routing with multiplicative stretch 3 (which means that the path used by the routing scheme can be up to three times longer than a shortest path) can be done with routing tables of Θ(√n) bits per node. The space lower bound is due to the existence of dense graphs with large girth. Dense graphs can be sparsified to subgraphs, called spanners, with various stretch guarantees. There are spanners with additive stretch guarantees (some even have constant additive stretch) but only very few additive routing schemes are known. In this paper, we give reasons why routing in unweighted graphs with additive stretch is difficult in the form of space lower bounds for general graphs and for planar graphs. We prove that any routing scheme using routing tables of size μ bits per node and addresses of poly-logarithmic length has additive stretch Ω(√n/μ) for general graphs, and Ω(√n/μ) for planar graphs. Routing with tables of size $O(n^{1/3})$ thus requires a polynomial additive stretch $Ω(n^{1/3}),$ whereas spanners with average degree $O(n^{1/3})$ and constant additive stretch exist for all graphs. Spanners, however sparse they are, do not tell us how to route. These bounds provide the first separation of sparse spanner problems and compact routing problems. On the positive side, we give an almost tight upper bound: we present the first non-trivial compact routing scheme with $o(log^{2}n)-bit$ addresses, additive stretch $O(n^{1/3}),$ and table size $O(n^{1/3})$ bits for all graphs with linear local tree-width such as planar, bounded-genus, and apex-minor-free graphs. Note: Asymptotic notation in this abstract suppresses factors logarithmic in n.
Starting Page	225
Ending Page	234
Page Count	10
File Format	PDF
ISBN	9781450307437
DOI	10.1145/1989493.1989526
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Shortest paths Compact routing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Roundtrip spanners and roundtrip routing in directed graphs

Efficient distributed source detection with limited bandwidth

New Routing Techniques and their Applications

Computing almost shortest paths

All-Pairs Almost Shortest Paths

Sparse spanners vs. compact routing (2011)

Alternative routing: k-shortest paths with limited overlap

Fast Algorithms for Constructing t-Spanners and Paths with Stretch t

Near-Linear Time Construction of Sparse Neighborhood Covers

Sparse spanners vs. compact routing

Similar Documents

Roundtrip spanners and roundtrip routing in directed graphs

Efficient distributed source detection with limited bandwidth

New Routing Techniques and their Applications

Computing almost shortest paths

All-Pairs Almost Shortest Paths

Sparse spanners vs. compact routing (2011)

Alternative routing: k-shortest paths with limited overlap

Fast Algorithms for Constructing t-Spanners and Paths with Stretch t

Near-Linear Time Construction of Sparse Neighborhood Covers

Sparse spanners vs. compact routing