Concepedia

Graph Property Testing

Graph Property Testing is a computational framework within sublinear algorithms that distinguishes whether a graph satisfies a fixed property or is far from satisfying it by examining only a small portion of the graph.

131

Publications

10.9K

Citations

170

Authors

106

Institutions

Publications per year

2017–2026

14

Parents

Publications

131

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Kellogg S. Booth, George S. Lueker · Journal of Computer and System Sciences · 1976 · 1.5K citations

, , +15

Property testing and its connection to learning and approximation

Oded Goldreich, Shari Goldwasser, Dana Ron · Journal of the ACM · 1998 · 1.1K citations · Full text

, , +14

Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Robert E. Tarjan, Mihalis Yannakakis · SIAM Journal on Computing · 1984 · 1.1K citations

, , +13

Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing

Christian Borgs, Jennifer Chayes, L. Lovász et al. · Advances in Mathematics · 2008 · 594 citations

, , +12

Taming verification hardness

Haichuan Shang, Ying Zhang, Xuemin Lin et al. · Proceedings of the VLDB Endowment · 2008 · 392 citations

, , +15

1–5 of 131

Authors

170

  1. NA
    Noga Alon

    Tel Aviv University, Israel

    20 publications · 1.6K citations

    17

    h-index

  2. EF
    Eldar Fischer

    Technion – Israel Institute of Technology, Israel

    15 publications · 1.1K citations

    14

    h-index

  3. AS
    A. Shapira

    Weizmann Institute of Science, Israel

    15 publications · 1.1K citations

    14

    h-index

  4. DR
    Dana Ron

    Tel Aviv University, Israel

    16 publications · 1.9K citations

    14

    h-index

  5. OG
    Oded Goldreich

    Weizmann Institute of Science, Israel

    12 publications · 2.2K citations

    11

    h-index

1–5 of 170

Institutions

106

  1. Tel Aviv University

    Tel Aviv, Israel

    22 h-index

    57 publications

    3.9K citations

  2. Weizmann Institute of Science

    Rehovot, Israel

    11 h-index

    15 publications

    3.7K citations

  3. Princeton University

    Princeton, United States

    11 h-index

    15 publications

    1.1K citations

  4. Technion – Israel Institute of Technology

    Haifa, Israel

    10 h-index

    18 publications

    634 citations

  5. University of Haifa

    Haifa, Israel

    9 h-index

    11 publications

    573 citations

  6. TU Dortmund University

    Dortmund, Germany

    8 h-index

    13 publications

    370 citations

  7. University of Warwick

    Coventry, United Kingdom

    7 h-index

    7 publications

    276 citations

  8. Georgia Institute of Technology

    Atlanta, United States

    7 h-index

    7 publications

    298 citations

1–8 of 106

Venues

  1. SIAM Journal on Computing

    17 publications · 2.1K citations

    16

    h-index

  2. Random Structures and Algorithms

    11 publications · 670 citations

    11

    h-index

  3. arXiv (Cornell University)

    Repository · 5 publications · 147 citations

    5

    h-index

  4. Algorithmica

    5 publications · 383 citations

    5

    h-index

  5. 4

    h-index

1–5