Loading...
Please wait, while we are loading the content...
Similar Documents
Engineering multi-level overlay graphs for shortest-path queries (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Holzer, Martin Schulz, Frank Wagner, Dorothea |
| Description | An overlay graph of a given graph G =(V,E) on a subset S ⊆ V is a graph with vertex set S that preserves some property of G. In particular, we consider variations of the multi-level overlay graph used in [21] to speed up shortestpath computations. In this work, we follow up and present general vertex selection criteria and strategies of applying these criteria to determine a subset S inducing an overlay graph. The main contribution is a systematic experimental study where we investigate the impact of selection criteria and strategies on multi-level overlay graphs and the resulting speed-up achieved for shortest-path queries. Depending on selection strategy and graph type, a centrality index criterion, a criterion based on planar separators, and vertex degree turned out to be good selection criteria. |
| File Format | |
| Language | English |
| Publisher Date | 2006-01-01 |
| Publisher Institution | IN: PROCEEDINGS OF THE EIGHT WORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS (ALENEX06), SIAM |
| Access Restriction | Open |
| Subject Keyword | Main Contribution Overlay Graph Good Selection Criterion Graph Type Selection Criterion Multi-level Overlay Graph Shortest-path Query Shortestpath Computation Planar Separator Systematic Experimental Study Selection Strategy Centrality Index Criterion Present General Vertex Selection Criterion |
| Content Type | Text |
| Resource Type | Article |
