A note on succinct representations of graphs

1986/12/01 by Christos H. Papadimitriou, Mihalis Yannakakis · 5 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Formal Methods in Verification #Radiation Effects in Electronics

paper · doi:10.1016/s0019-9958(86)80009-2

crossref issued 1986/12/01 · crossref published 1986/12/01 · crossref published-print 1986/12/01 · openalex publication_date 1986/12/01 · crossref created 2005/05/03 · crossref deposited 2019/01/26 · openalex created_date 2025/10/10 · crossref indexed 2026/04/01 · openalex updated_date 2026/06/11

Cited by

• Complexity and expressive power of logic programming
• Hardness of Approximation Between P and NP
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes
• Subclasses of presburger arithmetic and the weak EXP hierarchy
• NEXPTIME [wikipedia]