Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Density Independent Algorithms for Sparsifying k-Step Random Walks

Jindal, G., Kolev, P., Peng, R., & Sawlani, S. (2017). Density Independent Algorithms for Sparsifying k-Step Random Walks. Retrieved from http://arxiv.org/abs/1702.06110.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier
Latex : Density Independent Algorithms for Sparsifying $k$-Step Random Walks

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1702.06110.pdf (Preprint), 234KB
Name:
arXiv:1702.06110.pdf
Beschreibung:
File downloaded from arXiv at 2017-04-28 08:07
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Jindal, Gorav1, Autor           
Kolev, Pavel1, Autor           
Peng, Richard2, Autor
Sawlani, Saurabh2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Data Structures and Algorithms, cs.DS
 Zusammenfassung: We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2017-02-202017
 Publikationsstatus: Online veröffentlicht
 Seiten: 17 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1702.06110
URI: http://arxiv.org/abs/1702.06110
BibTex Citekey: DBLP:journals/corr/JindalKPS17
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: