Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems

DOI10.1137/S0097539795285254zbMath0911.68153OpenAlexW2011800734MaRDI 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

zbMATH Keywords

computational complexityVLSI designapproximation algorithmsCAD systemsPSPACE-hardnesshierarchical specificationsperiodic specifications

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)

Related Items (7)

Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies ⋮ On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ Unnamed Item ⋮ Cyclic-routing of unmanned aerial vehicles ⋮ Model-checking hierarchical structures ⋮ Fixpoint logics over hierarchical structures ⋮ Periodic constraint satisfaction problems: Tractable subclasses

This page was built for publication: Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems