Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs

DOI10.1137/0217068zbMath0673.05085OpenAlexW2022486658MaRDI QIDQ3826621

Thomas Lengauer, Egon Wanke

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217068

zbMATH Keywords

graph problemshierarchically graph descriptionhierarchically graph model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Connectivity (05C40)

Related Items

The complexity of connectivity problems on context-free graph languages, Efficient solutions of hierarchical systems of linear equations, The complexity of combinatorial problems with succinct input representation, Model-checking hierarchical structures, Bounded tree-width and LOGCFL, Fixpoint logics over hierarchical structures, Algorithms for graph problems on BNLC structured garphs, 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, Hierarchically specified unit disk graphs, Complexity of path-forming games, Finite graph automata for linear and boundary graph languages, On matroids and hierarchical graphs, A Parametrized Analysis of Algorithms on Hierarchical Graphs, The virtual feedback problem in hierarchical representations of combinational circuits, Hierarchically specified unit disk graphs