NDLI: Lower bounds for graph embeddings and combinatorial preconditioners

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

On delivery times in packet networks under adversarial traffic

Object location in realistic networks

Fighting against two adversaries: page migration in dynamic networks

Packet-mode policies for input-queued switches

Balanced graph partitioning

Scheduling against an adversarial network

Sharing the cost of multicast transmissions in wireless networks

A scalable lock-free stack algorithm

Effectively sharing a cache among threads

Improved combination of online algorithms for acceptance and rejection

Online algorithms for network design

Dynamic analysis of the arrow distributed protocol

Adaptive channel queue routing on k-ary n-cubes

Simple efficient load balancing algorithms for peer-to-peer systems

Online hierarchical cooperative caching

Parallelism versus memory allocation in pipelined router forwarding engines

Bi-criteria algorithm for scheduling jobs on cluster platforms

On achieving optimized capacity utilization in application overlay networks with multiple competing sessions

Selfish load balancing and atomic congestion games

DCAS is not a silver bullet for nonblocking algorithm design

Cache-oblivious shortest paths in graphs using buffer heap

Time complexity of practical parallel steiner point insertion algorithms

Expansion properties of (secure) wireless networks

Optimal early stopping uniform consensus in synchronous systems with process omission failures

Compact name-independent routing with minimum stretch

Consistent and compact data management in distributed storage systems

New results on web caching with request reordering

Lower bounds for graph embeddings and combinatorial preconditioners

On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs

Pagoda: a dynamic overlay network for routing, data management, and multicasting

How to route and tax selfish unsplittable traffic

Efficient orchestration of sub-word parallelism in media processors

Online algorithms for prefetching and caching on parallel disks

The inherent queuing delay of parallel packet switches

The effect of faults on network expansion

Writing-all deterministically and optimally using a non-trivial number of asynchronous processors

Geometric generalizations of the power of two choices

An NC algorithm for finding a maximal acyclic set in a graph

Efficient search in unstructured peer-to-peer networks

The potential in energy efficiency of a speculative chip-multiprocessor

Lower bounds for graph embeddings and combinatorial preconditioners

Content Provider	ACM Digital Library
Author	Richter, Peter C. Miller, Gary L.
Abstract	Given a general graph G, a fundamental problem is to find a spanning tree H that best approximates G by some measure. Often this measure is some combination of the congestion and dilation of an embedding of G into H. One example is the routing time p(G, H) ≤ O (congestion + dilation), the number of steps necessary to route pairwise demands G on network links H in the store-and-forward packet routing model. Another is the condition number kf(G, H) ≤ O (congestion · dilation), the square root of which bounds the number of iterations necessary to solve a linear system with coefficient matrix G preconditioned by H using the classical conjugate gradient method. The algorithmic applications of being able to find (efficiently) a good tree approximation H for a graph G are numerous; but what if no good tree exists.In this paper, we seek to identify the class of graphs G which are intrinsically difficult to approximate by a particular measure. It is easily seen that with respect to routing time, G is hardest to approximate by a tree H precisely when it contains either long cycles (which yield high dilation)or large separators (which yield high congestion). We show that with respect to condition number, the existence of long cycles or large separators in G is sufficient but not necessary or it to be hardest to approximate, by demonstrating a nearly-linear lower bound or the case in which G is a square mesh. The proof uses concepts from circuit theory, linear algebra, and geometry, and it generalizes to the case in which H is a spanning subgraph of G of Euler characteristic k. The result has consequences or the design of preconditioners or symmetric M-matrices and perhaps also of communication networks.
Starting Page	112
Ending Page	119
Page Count	8
File Format	PDF
ISBN	1581138407
DOI	10.1145/1007912.1007929
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-06-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Dilation Graph embeddings Congestion Preconditioning
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

Lower Bounds for Graph Embeddings and Combinatorial Preconditioners (2004)

Support-graph preconditioners (2006)

Lower bounds for graph embeddings via algebraic topology

Variable-Dilation Embeddings of Hypercubes into Star Graphs: Performance Metrics, Mapping Functions, and Routing (1996)

Support-graph preconditioners (2001)

Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes

Combinatorial Preconditioners for Scalar Elliptic Finite-Element Problems

Support-Graph Preconditioners (0)

Improved lower bounds for embeddings into $L_{1}$

Lower bounds for graph embeddings and combinatorial preconditioners

Similar Documents

Lower Bounds for Graph Embeddings and Combinatorial Preconditioners (2004)

Support-graph preconditioners (2006)

Lower bounds for graph embeddings via algebraic topology

Variable-Dilation Embeddings of Hypercubes into Star Graphs: Performance Metrics, Mapping Functions, and Routing (1996)

Support-graph preconditioners (2001)

Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes

Combinatorial Preconditioners for Scalar Elliptic Finite-Element Problems

Support-Graph Preconditioners (0)

Improved lower bounds for embeddings into $L_{1}$

Lower bounds for graph embeddings and combinatorial preconditioners