Loading...
Please wait, while we are loading the content...
Similar Documents
Collective Tree Spanners of Graphs (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Dragan, Feodor F. Yan, Chenyu Lomonosov, Irina |
| Description | In this paper we introduce a new notion of collective tree spanners. We say that a graph G =(V,E) admits a system of collective additive tree r-spanners if there is a system spanning trees of G such that for any two vertices x, y of G a spanning exists such that dT (x, y) dG (x, y)+r. Among other results, we show that any chordal graph, chordal bipartite graph or cocomparability graph admits a system of at most log 2 n collective additive tree 2--spanners and any c-chordal graph admits a system of at most log 2 n collective additive tree (2#c/2#)--spanners. Towards establishing these results, we present a general property for graphs, called (#, r)-- decomposition, and show that any (#, r)--decomposable graph G with n vertices admits a system of at most log 1/# n collective additive tree 2r-- spanners. We discuss also an application of the collective tree spanners to the problem of designing compact and e#cient routing schemes in graphs. |
| File Format | |
| Language | English |
| Publisher | Springer |
| Publisher Date | 2004-01-01 |
| Publisher Institution | SIAM Journal on Discrete Mathematics |
| Access Restriction | Open |
| Subject Keyword | Collective Additive Tree R-spanners Collective Additive Tree Collective Tree Spanner Chordal Bipartite Graph Chordal Graph C-chordal Graph Decomposable Graph New Notion General Property |
| Content Type | Text |
| Resource Type | Article |
