Loading...
Please wait, while we are loading the content...
Similar Documents
Lower Bounds for Graph Embeddings and Combinatorial Preconditioners (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Miller, Gary L. Richter, Peter C. |
| 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 ρ(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 κf(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 for it to be hardest to approximate, by demonstrating a nearly-linear lower bound for 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 for the design of preconditioners for symmetric M-matrices and perhaps also of communication networks. |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | Classical Conjugate Gradient Method Coefficient Matrix Algorithmic Application Communication Network General Graph Spanning Tree Good Tree Exists Fundamental Problem Graph Embeddings Symmetric M-matrices Linear Algebra Square Mesh Long Cycle Large Separator Pairwise Demand Particular Measure Combinatorial Preconditioners Circuit Theory Linear System Network Link Condition Number Square Root Congestion Dilation High Congestion Store-and-forward Packet Euler Characteristic High Dilation Good Tree Approximation Routing Time |
| Content Type | Text |
| Resource Type | Article |
