Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
DOI10.1137/S0097539795285254zbMATH Open0911.68153OpenAlexW2011800734MaRDI QIDQ4210093FDOQ4210093
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
Recommendations
computational complexityapproximation algorithmsVLSI designCAD systemsPSPACE-hardnesshierarchical specificationsperiodic specifications
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)
Cited In (12)
- Title not available (Why is that?)
- Model-checking hierarchical structures
- Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies
- Title not available (Why is that?)
- The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
- On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
- Title not available (Why is that?)
- Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)
- Fixpoint logics over hierarchical structures
- Periodic constraint satisfaction problems: Tractable subclasses
- Cyclic-routing of unmanned aerial vehicles
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
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)
