Succinct representations of graphs
From MaRDI portal
Publication:3325058
DOI10.1016/S0019-9958(83)80004-7zbMath0538.68053OpenAlexW1982538209MaRDI QIDQ3325058
Publication date: 1983
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(83)80004-7
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (39)
Languages represented by Boolean formulas ⋮ Complexity, appeal and challenges of combinatorial games ⋮ Trading uninitialized space for time ⋮ The complexity of combinatorial problems with succinct input representation ⋮ Equality Testing of Compressed Strings ⋮ Specular Sets ⋮ Compressed Tree Canonization ⋮ On the complexity of kings ⋮ Approximating schedules for dynamic process graphs efficiently ⋮ The minimum oracle circuit size problem ⋮ Processing succinct matrices and vectors ⋮ Sequential Relational Decomposition ⋮ Synthesis for Multi-weighted Games with Branching-Time Winning Conditions ⋮ The complexity of searching implicit graphs ⋮ The complexity gap in the static analysis of cache accesses grows if procedure calls are added ⋮ Model-checking hierarchical structures ⋮ Automated competitive analysis of real-time scheduling with graph games ⋮ The difference and truth-table hierarchies for NP ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ The computational complexity of graph problems with succinct multigraph representation ⋮ The complexity of approximating PSPACE-complete problems for hierarchical specifications ⋮ On matroids and hierarchical graphs ⋮ The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems ⋮ Succinct circuit representations and leaf language classes are basically the same concept ⋮ The complexity of searching succinctly represented graphs ⋮ CNF and DNF succinct graph encodings ⋮ Hierarchically specified unit disk graphs ⋮ Representing graphs implicitly using almost optimal space ⋮ Functions computable in polynomial space ⋮ On matroids and hierarchical graphs ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ A Parametrized Analysis of Algorithms on Hierarchical Graphs ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ A framework for analysing state-abstraction methods ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Linear connectivity problems in directed hypergraphs ⋮ Symbolic model checking for \(\mu\)-calculus requires exponential time ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Ranking Sets of Objects: The Complexity of Avoiding Impossibility Results
This page was built for publication: Succinct representations of graphs
