Concepedia

Sublinear-time Graph Algorithms

Sublinear-Time Graph Algorithms is a class of algorithmic methods in theoretical computer science that, given access to a graph via queries, solves computational problems in time strictly sublinear in the size of the input graph, thereby distinguishing itself from traditional graph algorithms that require at least linear time.

91

Publications

10.7K

Citations

164

Authors

106

Institutions

Publications per year

2017–2026

16

Parents

Publications

91

Depth-First Search and Linear Graph Algorithms

Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations

, , +16

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

B. Courcelle, Johann A. Makowsky, Udi Rotics · Theory of Computing Systems · 2000 · 788 citations

, , +14

Depth-first search and linear graph algorithms

Robert E. Tarjan · 1971 · 655 citations

, , +16

Linear time algorithm for isomorphism of planar graphs (Preliminary Report)

John E. Hopcroft, Jin Kue Wong · 1974 · 343 citations

, , +10

Spanners and emulators with sublinear distance errors

Mikkel Thorup, Uri Zwick · Symposium on Discrete Algorithms · 2006 · 132 citations

, , +13

1–5 of 91

Authors

164

  1. DR
    Dana Ron

    Tel Aviv University, Israel

    8 publications · 333 citations

    8

    h-index

  2. RE
    Robert E. Tarjan

    Princeton University, United States

    4 publications · 6.7K citations

    4

    h-index

  3. FK
    Fabian Kühn

    ETH Zurich, Switzerland

    3 publications · 57 citations

    3

    h-index

  4. DE
    David Eppstein

    University of California, Irvine, United States

    3 publications · 48 citations

    3

    h-index

  5. KO
    Krzysztof Onak

    Massachusetts Institute of Technology, United States

    3 publications · 98 citations

    3

    h-index

1–5 of 164

Institutions

106

  1. Tel Aviv University

    Tel Aviv, Israel

    12 h-index

    38 publications

    1.3K citations

  2. University of Bergen

    Bergen, Norway

    4 h-index

    9 publications

    263 citations

  3. University of California, Irvine

    Irvine, United States

    3 h-index

    3 publications

    48 citations

  4. Stanford University

    Stanford, United States

    3 h-index

    3 publications

    779 citations

  5. California University of Pennsylvania

    California, United States

    3 h-index

    6 publications

    223 citations

  6. University of Copenhagen

    Copenhagen, Denmark

    3 h-index

    3 publications

    105 citations

  7. University of Freiburg

    Freiburg im Breisgau, Germany

    3 h-index

    3 publications

    57 citations

  8. Utrecht University

    Utrecht, The Netherlands

    2 h-index

    4 publications

    119 citations

1–8 of 106

Venues

  1. SIAM Journal on Computing

    6 publications · 6.2K citations

    6

    h-index

  2. Symposium on Discrete Algorithms

    Conference · 6 publications · 242 citations

    6

    h-index

  3. Information Processing Letters

    5 publications · 89 citations

    5

    h-index

  4. Algorithmica

    4 publications · 106 citations

    4

    h-index

  5. Discrete Applied Mathematics

    4 publications · 102 citations

    4

    h-index

1–5