A Parametrized Analysis of Algorithms on Hierarchical Graphs

DOI10.1142/S0129054119400252zbMath1427.68240OpenAlexW2973900959MaRDI QIDQ5205039

Orna Kupferman, Rachel Faran

Publication date: 10 December 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054119400252

zbMATH Keywords

graph theoryhierarchical systemsparametrized analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Improved model checking of hierarchical systems
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Complexity of equivalence problems for concurrent systems of finite agents
• On the complexity of verifying concurrent transition systems
• Maximal Flow Through a Network
• Hierarchical Network Formation Games
• Succinct representations of graphs
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Optimal flows in networks with multiple sources and sinks
• On the power of bounded concurrency I
• Formal-Language-Constrained Path Problems
• The Matching Polytope has Exponential Extension Complexity
• Linear-time computation of optimal subgraphs of decomposable graphs
• Finding Regular Simple Paths in Graph Databases
• Labeled shortest paths in digraphs with negative and positive edge weights
• An automata-theoretic approach to branching-time model checking
• Program Complexity in Hierarchical Module Checking