A Parametrized Analysis of Algorithms on Hierarchical Graphs

DOI10.1142/S0129054119400252MaRDI QIDQ5205039zbMATH OpenOpenAlexFDO

Authors Rachel Faran, Orna Kupferman

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)

Recommendations

• A parametrized analysis of algorithms on hierarchical graphs
• scientific article; zbMATH DE number 45244
• Algorithms and experiments for parameterized approaches to hard graph problems
• The hierarchical structure of graph searches
• scientific article; zbMATH DE number 4009832
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Deriving a class of layer-oriented graph algorithms
• scientific article; zbMATH DE number 4016952
• Parameterized algorithms for non-separating trees and branchings in digraphs

Cites work

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

Cited in

(4)

• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• A parametrized analysis of algorithms on hierarchical graphs
• scientific article; zbMATH DE number 4009832 (Why is no real title available?)
• FO-query enumeration over SLP-compressed structures of bounded degree

This page was built for publication: A Parametrized Analysis of Algorithms on Hierarchical Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205039)