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

approximation algorithmsCAD systemscomputational complexityhierarchical specificationsperiodic specificationsPSPACE-hardnessVLSI design

Mathematics Subject Classification ID

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

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

(14)

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

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)