Concepedia

Graph Problems In Nc

Graph Problems in NC is a theoretical framework in parallel complexity theory that identifies and classifies computational problems on graphs solvable by a parallel algorithm in polylogarithmic time using a polynomial number of processors.

45

Publications

3K

Citations

71

Authors

59

Institutions

Publications per year

2017–2026

4

Parents

Publications

45

A new approach to the minimum cut problem

David R. Karger, Clifford Stein · Journal of the ACM · 1996 · 495 citations · Full text

, , +8

Finding minimum-cost circulations by canceling negative cycles

Andrew V. Goldberg, Robert E. Tarjan · Journal of the ACM · 1989 · 344 citations · Full text

, , +14

The Algorithmic Aspects of the Regularity Lemma

Noga Alon, Richard A. Duke, Hanno Lefmann et al. · Journal of Algorithms · 1994 · 322 citations

, , +13

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

Harry B. Hunt, Madhav Marathe, Venkatesh Babu Radhakrishnan et al. · Journal of Algorithms · 1998 · 317 citations

, , +12

External-memory graph algorithms

Yi‐Jen Chiang, Michael T. Goodrich, Edward F. Grove et al. · KU ScholarWorks (The University of Kansas) · 1995 · 279 citations · Full text

, , +9

1–5 of 45

Authors

71

  1. RE
    Robert E. Tarjan

    Princeton University, United States

    3 publications · 416 citations

    3

    h-index

  2. VV
    Vijay V. Vazirani

    Georgia Institute of Technology, United States

    3 publications · 112 citations

    3

    h-index

  3. EM
    Eugene M. Luks

    University of Oregon, United States

    3 publications · 178 citations

    3

    h-index

  4. TT
    Thomas Thierauf

    Universität Ulm, Germany

    2 publications · 55 citations

    2

    h-index

  5. MN
    Moni Naor

    Weizmann Institute of Science, Israel

    2 publications · 64 citations

    2

    h-index

1–5 of 71

Institutions

59

  1. Stanford University

    Stanford, United States

    5 h-index

    6 publications

    520 citations

  2. Princeton University

    Princeton, United States

    4 h-index

    4 publications

    431 citations

  3. University of Chicago

    Chicago, United States

    4 h-index

    4 publications

    207 citations

  4. Eötvös Loránd University

    Budapest, Hungary

    3 h-index

    3 publications

    195 citations

  5. IBM Research - Almaden

    San Jose, United States

    2 h-index

    2 publications

    78 citations

  6. Hochschule Aalen

    Aalen, Germany

    2 h-index

    3 publications

    96 citations

  7. Massachusetts Institute of Technology

    Cambridge, United States

    2 h-index

    4 publications

    525 citations

  8. Tel Aviv University

    Tel Aviv, Israel

    2 h-index

    2 publications

    70 citations

1–8 of 59

Venues

  1. SIAM Journal on Computing

    5 publications · 132 citations

    5

    h-index

  2. Journal of the ACM

    JACM · 3 publications · 875 citations

    3

    h-index

  3. Journal of Algorithms

    2 publications · 639 citations

    2

    h-index

  4. HAL (Le Centre pour la Communication Scientifique Directe)

    Repository · 2 publications · 107 citations

    2

    h-index

  5. 1

    h-index

1–5