Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
From MaRDI portal
Publication:4210093
DOI10.1137/S0097539795285254zbMath0911.68153MaRDI QIDQ4210093
Richard E. Stearns, Venkatesh Radhakrishnan, Harry B. III Hunt, Madhav V. Marathe
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539795285254
computational complexity; VLSI design; approximation algorithms; CAD systems; PSPACE-hardness; hierarchical specifications; periodic specifications
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
05C40: Connectivity
Related Items
Model-checking hierarchical structures, Periodic constraint satisfaction problems: Tractable subclasses, Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies, Cyclic-routing of unmanned aerial vehicles, Fixpoint logics over hierarchical structures, Unnamed Item, On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations