Fast approximation of steiner trees in large graphs

Andrey Gubichev, Thomas Neumann

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

11 Zitate (Scopus)

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.

OriginalspracheEnglisch
TitelCIKM 2012 - Proceedings of the 21st ACM International Conference on Information and Knowledge Management
Seiten1497-1501
Seitenumfang5
DOIs
PublikationsstatusVeröffentlicht - 2012
Veranstaltung21st ACM International Conference on Information and Knowledge Management, CIKM 2012 - Maui, HI, USA/Vereinigte Staaten
Dauer: 29 Okt. 20122 Nov. 2012

Publikationsreihe

NameACM International Conference Proceeding Series

Konferenz

Konferenz21st ACM International Conference on Information and Knowledge Management, CIKM 2012
Land/GebietUSA/Vereinigte Staaten
OrtMaui, HI
Zeitraum29/10/122/11/12

Fingerprint

Untersuchen Sie die Forschungsthemen von „Fast approximation of steiner trees in large graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren