Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems

DOI10.1137/S0097539795285254MaRDI QIDQ4210093zbMATH OpenOpenAlexFDO

Authors R. E. Stearns, V. Radhakrishnan, Madhav V. Marathe, H. B. III Hunt

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 complexityapproximation algorithmsVLSI designCAD systemsPSPACE-hardnesshierarchical specificationsperiodic specifications

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 751134
• The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
• scientific article; zbMATH DE number 1560343
• Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)

Cited in

(12)

• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• scientific article; zbMATH DE number 751134 (Why is no real title available?)
• Model-checking hierarchical structures
• Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies
• scientific article; zbMATH DE number 1560343 (Why is no real title available?)
• The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
• On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
• scientific article; zbMATH DE number 1335885 (Why is no real title available?)
• Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)
• Periodic constraint satisfaction problems: Tractable subclasses
• Fixpoint logics over hierarchical structures
• Cyclic-routing of unmanned aerial vehicles

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

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