NDLI: Sparse distance preservers and additive spanners

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

Optimal parallel selection

Algorithms for power savings

Sublogarithmic approximation for telephone multicast: path out of jungle (extended abstract)

Browsing around a digital library

Binary space partitions for 3D subdivisions

Improved bounds on the average length of longest common subsequences

Certifying algorithms for recognizing interval graphs and permutation graphs

Optimizing misdirection

Pass efficient algorithms for approximating large matrices

Certifying and repairing solutions to large LPs how good are LP-solvers?

The flow complex: a data structure for geometric modeling

Random walks on the vertices of transportation polytopes with constant number of sources

Space-efficient finger search on degree-balanced search trees

Data streams: algorithms and applications

Sparse distance preservers and additive spanners

Improved results for directed multicut

A note on the set systems used for broadcast encryption

Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk

Lower bounds for embedding edit distance into normed spaces

Better algorithms for high-dimensional proximity problems via asymmetric embeddings

On the rectilinear crossing number of complete graphs

Edge disjoint paths revisited

Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time

Who cares about permanents?

Between O(nm) and $O(n^{α})$

Efficient sequences of trials

Competitive queueing policies for QoS switches

Smaller core-sets for balls

Inferring tree topologies using flow tests

High-order entropy-compressed text indexes

Selection with monotone comparison costs

Dynamic TCP acknowledgement: penalizing long delays

On the performance of user equilibria in traffic networks

Allocating vertex π-guards in simple polygons via pseudo-triangulations

Directed scale-free graphs

Dominating sets in planar graphs: branch-width and exponential speed-up

Online learning in online auctions

Rangesum histograms

An improved approximation algorithm for the 0-extension problem

Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio

Smaller explicit superconcentrators

Multi-embedding and path approximation of metric spaces

Algorithms for k-colouring and finding maximal independent sets

Lower bounds for collusion-secure fingerprinting

Non-independent randomized rounding

Embedding k-outerplanar graphs into ℓ1

Lower bounds for external memory dictionaries

Matching planar maps

A new approximation algorithm for the asymmetric TSP with triangle inequality

Compact representations of separable graphs

Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons

Pursuit-evasion with imprecise target location

Dynamic routing on networks with fixed-size buffers

Zonotopes as bounding volumes

Wavelength assignment and generalized interval graph coloring

Multidimensional matching and fast search in suffix trees

Property testing of data dimensionality

Approximately optimal control of fluid networks

Faster approximation algorithms for the minimum latency problem

Straight-skeleton based contour interpolation

The cover time of sparse random graphs.

Quick and good facility location

An approximate truthful mechanism for combinatorial auctions with single parameter agents

Approximation of functions over redundant dictionaries using coherence

Packing Steiner trees

On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres

A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma

Maintaining all-pairs approximate shortest paths under deletion of edges

Approximation algorithm for embedding metrics into a two-dimensional space

Equitable colorings with constant number of colors

Quantum property testing

Minimizing weighted flow time

Embeddings and non-approximability of geometric problems

Online paging with arbitrary associativity

Dynamic generators of topologically embedded graphs

Approximating asymmetric maximum TSP

Labeling schemes for small distances in trees

A 5/4-approximation algorithm for minimum 2-edge-connectivity

Unconditional proof of tightness of Johnson bound

Dynamic construction of Bluetooth scatternets of fixed degree and low diameter

Sublinear-time approximation of Euclidean minimum spanning tree

An improved approximation algorithm for the partial latin square extension problem

Inplace 2D matching in compressed images

Comparing top k lists

Minimum cost flows over time without intermediate storage

Data migration to minimize the average completion time

Möbius-invariant natural neighbor interpolation

Perfect matchings in random graphs with prescribed minimal degree

Chain decompositions and independent trees in 4-connected graphs

Competitiveness via consensus

Counting inversions in lists

Integrality ratio for group Steiner trees and directed steiner trees

Perturbations and vertex removal in a 3D delaunay triangulation

A spectral technique for random satisfiable 3CNF formulas

A faster and simpler fully dynamic transitive closure

On the complexity of distance-based evolutionary tree reconstruction

Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph

Quantum algorithms for some hidden shift problems

A combinatorial algorithm for computing a maximum independent set in a t-perfect graph

The set-associative cache performance of search trees

Computing homotopic shortest paths in the plane

The k-traveling repairman problem

On $AC^{0}$ implementations of fusion trees and atomic heaps

Fault-tolerant facility location

Deterministic identity testing for multivariate polynomials

Scheduling techniques for media-on-demand

An approximation algorithm for cutting out convex polygons

Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs

The similarity metric

Root comparison techniques applied to computing the additively weighted Voronoi diagram

Random MAX SAT, random MAX CUT, and their phase transitions

Computing strongly connected components in a linear number of symbolic steps

Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time

Directed graphs requiring large numbers of shortcuts

Sparse distance preservers and additive spanners

Content Provider	ACM Digital Library
Author	Coppersmith, Don Bollobás, Béla Elkin, Michael
Abstract	For an unweighted graph G = (V, E), G′ = (V, E′) is a subgraph if E′ ⊆ E, and G″ = (V″, E″, ω) is a Steiner graph if V ⊆ V″, and for any pair of vertices u, w ∈ V, the distance bet-ween them in G″(denoted dG″, (u, w)) is at least the distance between them in G (denoted da(u, w)).In this paperwe introduce the notion of distance preserver. A subgraph (resp., Steiner graph) G′ of a graph G is a subgraph (resp., Steiner) D-preserver of G if for every pair of vertices u, w ∈ V with dG(u, w) ≥ D, dG′, (u, w) = dG(u, w). We show that anygraph (resp., digraph) has a subgraph D-preserver with at most $O(n^{2}/D)$ edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains $Ω(n^{2}/D)$ edges. However, we show that if one allows a directed Steiner (or, shortly, diS-teiner) D-preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner D-preserver with $O(n^{2}.log$ D/D.log n arcs, and that this result is tight up to a constant factor.We also study D-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation ofdistances between pairs of vertices that are at distance at least D one from another. We show that there exists a D-preserving labeling scheme with labels of size $O(n/Dlog^{2}$ n), and that labels of size Ω(n/D log D) are required for any D-preserving labeling scheme.Finally, we study additive spanners. A subgraph G′ of an undirected graph G = (V, E) is its additive β-spanner if for any pair of vertices u, w ∈ V, dG′, (u, w) ≤ dG(u, w)+β. It is known that for any n-vertex graph there exists an additive 2-spanner with $O(n^{3/2})$ edges, and an additive Steiner 4-spanner with $O(n^{4/3})$ edges. However, no construction of additive spanners with $o(n^{3/2})$ edges or Steiner additive spanners with $o(n^{4/3})$ edges are known so far. We devise a construction of additive $O(2^{1/Δ}n^{(1-Δ)}[1/Δ]--2/[1/Δ]--1)-spanner$ with $O(n^{1+Δ})$ edges for any graph and any Δ < 0.
Starting Page	414
Ending Page	423
Page Count	10
File Format	PDF
ISBN	0898715385
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-01-12
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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