Concepedia

Single-source Shortest Paths

Single-Source Shortest Paths is a computational graph theory problem that, given a directed or undirected graph with non-negative edge weights and a designated source vertex, determines the shortest path distances from the source to all other vertices in the graph.

208

Publications

14.3K

Citations

420

Authors

198

Institutions

Publications per year

2017–2026

49

Variants

Sssp

Parents

Publications

208

Fibonacci heaps and their uses in improved network optimization algorithms

Michael L. Fredman, Robert E. Tarjan · Journal of the ACM · 1987 · 2.7K citations · Full text

, , +16

Efficient Algorithms for Shortest Paths in Sparse Networks

D. Barton Johnson · Journal of the ACM · 1977 · 1K citations · Full text

, , +12

Undirected single-source shortest paths with positive integer weights in linear time

Mikkel Thorup · Journal of the ACM · 1999 · 441 citations · Full text

, , +12

Faster Shortest-Path Algorithms for Planar Graphs

Monika Henzinger, Philip N. Klein, Satish Rao et al. · Journal of Computer and System Sciences · 1997 · 410 citations · Full text

, , +16

CENTRALITY ESTIMATION IN LARGE NETWORKS

Ulrik Brandes, Christian Pich · International Journal of Bifurcation and Chaos · 2007 · 383 citations · Full text

, , +11

1–5 of 208

Authors

420

  1. DN
    Danupon Nanongkai

    University of Vienna, Austria

    9 publications · 581 citations

    9

    h-index

  2. MT
    Mikkel Thorup

    AT&T (United States), United States

    8 publications · 918 citations

    8

    h-index

  3. MH
    Monika Henzinger

    University of Vienna, Austria

    7 publications · 779 citations

    7

    h-index

  4. KP
    Keshav Pingali

    The University of Texas at Austin, United States

    6 publications · 218 citations

    6

    h-index

  5. PN
    Philip N. Klein

    Brown University, United States

    6 publications · 765 citations

    6

    h-index

1–5 of 420

Institutions

198

  1. AT&T (United States)

    Bedminster, United States

    10 h-index

    12 publications

    4.1K citations

  2. Carnegie Mellon University

    Pittsburgh, United States

    9 h-index

    20 publications

    495 citations

  3. The University of Texas at Austin

    Austin, United States

    9 h-index

    20 publications

    757 citations

  4. Tel Aviv University

    Tel Aviv, Israel

    8 h-index

    11 publications

    353 citations

  5. Max Planck Institute for Informatics

    Saarbrücken, Germany

    8 h-index

    14 publications

    476 citations

  6. University of Vienna

    Vienna, Austria

    7 h-index

    11 publications

    527 citations

  7. John Brown University

    Siloam Springs, United States

    6 h-index

    9 publications

    546 citations

  8. University of Copenhagen

    Copenhagen, Denmark

    6 h-index

    8 publications

    275 citations

1–8 of 198

Venues

  1. Journal of the ACM

    JACM · 7 publications · 4.4K citations

    7

    h-index

  2. SIAM Journal on Computing

    6 publications · 822 citations

    6

    h-index

  3. IEEE Transactions on Parallel and Distributed Systems

    TPDS · 5 publications · 356 citations

    5

    h-index

  4. Journal of Algorithms

    5 publications · 285 citations

    5

    h-index

  5. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 4 publications · 68 citations

    4

    h-index

1–5