A note on succinct representations of graphs
From MaRDI portal
Publication:4725746
DOI10.1016/S0019-9958(86)80009-2zbMath0616.68041OpenAlexW2065939997WikidataQ56387785 ScholiaQ56387785MaRDI QIDQ4725746
Mihalis Yannakakis, Christos H. Papadimitriou
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80009-2
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (31)
Languages represented by Boolean formulas ⋮ Trading uninitialized space for time ⋮ Equality Testing of Compressed Strings ⋮ Mean-payoff games with partial observation ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Approximating schedules for dynamic process graphs efficiently ⋮ On regular realizability problems ⋮ The minimum oracle circuit size problem ⋮ Sequential Relational Decomposition ⋮ On the Structure of Solution-Graphs for Boolean Formulas ⋮ The complexity of searching implicit graphs ⋮ The complexity gap in the static analysis of cache accesses grows if procedure calls are added ⋮ Conversational recommendation: theoretical model and complexity analysis ⋮ The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. ⋮ Model-checking hierarchical structures ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ The computational complexity of graph problems with succinct multigraph representation ⋮ Why not negation by fixpoint? ⋮ The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems ⋮ The complexity of searching succinctly represented graphs ⋮ CNF and DNF succinct graph encodings ⋮ Representing graphs implicitly using almost optimal space ⋮ On matroids and hierarchical graphs ⋮ Pruning external minimality checking for answer set programs using semantic dependencies ⋮ Answers set programs for non-transferable utility games: expressiveness, complexity and applications ⋮ Succinct representation, leaf languages, and projection reductions ⋮ On the Complexity of Value Iteration ⋮ Linear connectivity problems in directed hypergraphs ⋮ Succinctness as a source of complexity in logical formalisms ⋮ On the complexity of data disjunctions.
This page was built for publication: A note on succinct representations of graphs
