Name
Abstract | ||
|---|---|---|
Finding the minimum connected subtree of a graph that contains a given set of nodes (i.e., the Steiner tree problem) is a fundamental operation in keyword search in graphs, yet it is known to be NP-hard. Existing approximation techniques either make use of the heavy indexing of the graph, or entirely rely on online heuristics. In this paper we bridge the gap between these two extremes and present a scalable landmark-based index structure that, combined with a few lightweight online heuristics, yields a fast and accurate approximation of the Steiner tree. Our solution handles real-world graphs with millions of nodes and provides an approximation error of less than 5% on average. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2396761.2398460 | CIKM |
Keywords | Field | DocType |
steiner tree,approximation technique,fundamental operation,steiner tree problem,lightweight online heuristics,approximation error,accurate approximation,real-world graph,heavy indexing,online heuristics,fast approximation,large graph,steiner trees,graph databases | Data mining,Discrete mathematics,Block graph,Mathematical optimization,Computer science,Steiner tree problem,Tree (data structure),Heuristics,Graph product,Pathwidth,1-planar graph,Approximation error | Conference |
Citations | PageRank | References |
3 | 0.39 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrey Gubichev | 1 | 263 | 11.88 |
| Thomas Neumann | 2 | 2523 | 156.50 |