NDLI: Bounded-leg distance and reachability oracles

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

Fast dimension reduction using Rademacher series on dual BCH codes

Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections

A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods

Explicit constructions for compressed sensing of sparse signals

Improved distance sensitivity oracles via random sampling

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

Holographic algorithms with unsymmetric signatures

The UGC hardness threshold of the $ℓ_{p}$ Grothendieck problem

Succinct approximate convex pareto curves

Efficient reductions among lattice problems

Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles

Greedy drawings of triangulations

Maintaining deforming surface meshes

Exact and efficient 2D-arrangements of arbitrary algebraic curves

On properties of random dissections and triangulations

Graph algorithms for biological systems analysis

Adaptive local ratio

Two-phase greedy algorithms for some classes of combinatorial linear programs

Analysis of greedy approximations with nonsubmodular potential functions

Yet another algorithm for dense max cut: go greedy

Computing large matchings fast

A fractional model of the border gateway protocol (BGP)

Minimizing average latency in oblivious routing

Distributed broadcast in unknown radio networks

The power of memory in randomized broadcasting

Competitive queue management for latency sensitive packets

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Product growth and mixing in finite groups

Concatenated codes can achieve list-decoding capacity

Noisy sorting without resampling

Algorithms for the coalitional manipulation problem

On allocations that maximize fairness

On the value of coordination in network design

Auctions for structured procurement

Fast load balancing via bounded best response

(Almost) optimal coordination mechanisms for unrelated machine scheduling

Ultra-low-dimensional embeddings for doubling metrics

Earth mover distance over high-dimensional spaces

Almost Euclidean subspaces of $ℓ^{N}_{1}$ via expander codes

Embedding metric spaces in their intrinsic dimension

Optimal universal graphs with deterministic embedding

Fast and reliable reconstruction of phylogenetic trees with very short edges

Trace reconstruction with constant deletion probability and related results

Improved string reconstruction over insertion-deletion channels

Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly

Approximating general metric distances between a pattern and a text

A near-linear time algorithm for computing replacement paths in planar directed graphs

Bounded-leg distance and reachability oracles

A nearly linear time algorithm for the half integral disjoint paths packing

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Nondecreasing paths in a weighted graph or: how to optimally read a train schedule

Broadcast scheduling: algorithms and complexity

Graph balancing: a special case of scheduling unrelated parallel machines

Non-clairvoyant scheduling with precedence constraints

Provably good multicore cache performance for divide-and-conquer algorithms

Balls and bins with structure: balanced allocations on hypergraphs

Arc-disjoint in-trees in directed graphs

Finding one tight cycle

Set connectivity problems in undirected graphs and the directed Steiner network problem

Matroid intersection, pointer chasing, and Young's seminormal representation of $S_{n}$

Iterated rounding algorithms for the smallest k-edge connected spanning subgraph

Shuffling cards, adding numbers, and symmetric functions

On the bichromatic k-set problem

Geodesic Delaunay triangulation and witness complex in the plane

Minimum weight convex Steiner partitions

Improved algorithms for fully dynamic geometric spanners and geometric routing

On the connectivity of dynamic random geometric graphs

Improved algorithmic versions of the Lovász Local Lemma

L(2,1)-labelling of graphs

Catalan structures and dynamic programming in H-minor-free graphs

Computing excluded minors

An algorithm for improving graph partitions

Improved algorithms for orienteering and related problems

Approximation algorithms for labeling hierarchical taxonomies

Fast approximation of the permanent for very dense problems

Approximating TSP on metrics with bounded global growth

Fully polynomial time approximation schemes for stochastic dynamic programs

On distributing symmetric streaming computations

Tight lower bounds for selection in randomly ordered streams

On distance to monotonicity and longest increasing subsequence of a data stream

Declaring independence via the sketching of sketches

Why simple hash functions work: exploiting the entropy in a data stream

Maximum overhang

Deterministic random walks on regular trees

Quasirandom rumor spreading

Universality of random graphs

The effect of induced subgraphs on quasi-randomness

Clustering for metric and non-metric distance measures

Metric clustering via consistent labeling

On clustering to minimize the sum of radii

A constant factor approximation algorithm for k-median clustering with outliers

Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension

The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond

Designing networks with good equilibria

Ascending auctions for integral (poly)matroids with concave nondecreasing separable values

Fast algorithms for finding proper strategies in game trees

Incentive compatible regression learning

Space-efficient dynamic orthogonal point location, segment intersection, and range reporting

In-place 2-d nearest neighbor search

Distribution-sensitive point location in convex subdivisions

Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm

Sampling algorithms and coresets for $ℓ_{p}$ regression

Stochastic analyses for online combinatorial optimization problems

Online make-to-order joint replenishment model: primal dual competitive algorithms

Parallel monotonicity reconstruction

Better bounds for online load balancing on unrelated machines

Online budgeted matching in random input models with applications to Adwords

Computational advertising

Linked decompositions of networks and the power of choice in Polya urns

A local algorithm for finding dense subgraphs

PageRank and the random surfer model

Charity auctions on social networks

On the approximability of influence in social networks

Fast asynchronous byzantine agreement and leader election with full information

Unconditionally reliable message transmission in directed networks

A tight lower bound for parity in noisy communication networks

Ranged hash functions and the price of churn

Algorithms for distributed functional monitoring

Real-time indexing over fixed finite alphabets

Finding an optimal tree searching strategy in linear time

Dynamic optimality for skip lists and B-trees

Splay trees, Davenport-Schinzel sequences, and the deque conjecture

Fully dynamic algorithm for graph spanners with poly-logarithmic update time

SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems

Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities

Lower-bounded facility location

A plant location guide for the unsure

Approximating connected facility location problems via random facility sampling and core detouring

The hiring problem and Lake Wobegon strategies

Weak ε-nets and interval chains

Robust cost colorings

Comparing the strength of query types in property testing: the case of testing k-colorability

Sampling stable marriages: why spouse-swapping won't work

On stars and Steiner stars

Cutting cycles of rods in space: hardness and approximation

Empty-ellipse graphs

Recognizing partial cubes in quadratic time

Approximating geometric coverage problems

Bounded-leg distance and reachability oracles

Content Provider	ACM Digital Library
Author	Pettie, Seth Duan, Ran
Abstract	In a weighted, directed graph an L-bounded leg path is one whose constituent edges have length at most L. For any fixed L, computing L-bounded leg shortest paths is just as easy as the standard shortest path algorithm. In this paper we study approximate distance oracles (and reachability oracles) for bounded leg path problems, where the leg bound L is not known in advance, but forms part of the query. Bounded-leg path problems are more complicated than standard shortest path problems because the number of distinct shortest paths between two vertices (over all leg bounds) could be as large as the number of edges in the graph. The bounded leg constraint models situations where there is some limited resource that must be spent when traversing an edge. For example, the size of a fuel tank or the life of a battery places a hard limit on how far a vehicle can travel in one leg before refueling or recharging. Someone making a long road trip may place a hard limit on how many hours they are willing to drive in any one day. Our main result is a nearly optimal algorithm for preprocessing a directed graph in order to answer approximate bounded leg distance and bounded leg shortest path queries. In particular, we can preprocess any graph in $Õ(n^{3})$ time, producing a data structure with size $Õ(n^{2})$ that answers (1 + ∈)-approximate bounded leg distance queries in O(log log n) time. If the corresponding (1 + ∈)-approximate shortest path has l edges it can be returned in O(l log log n) time. These bounds are all within polylog(n) factors of the best standard all-pairs shortest path algorithm and improve substantially the previous best bounded leg shortest path algorithm, whose preprocessing time and space are $O(n^{4})$ and $Õ(n^{2.5}).$ We also consider bounded leg oracles in other situations. In the context of planar directed graphs we give a time-space tradeoff for answering bounded leg reachability queries. For any k ≥ 2 we can build a data structure with size $O(kn^{1+1/k})$ that answers reachability queries in time $Õ(n^{k™1/2k}).$
Starting Page	436
Ending Page	445
Page Count	10
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-01-20
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