The complexity of approximating PSPACE-complete problems for hierarchical specifications

DOI10.1007/3-540-56939-1_63zbMath1422.68128arXivmath/9409225OpenAlexW2138820476MaRDI QIDQ4630250

S. S. Ravi, Madhav V. Marathe, Harry B. III Hunt

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9409225

zbMATH Keywords

vertex coververtex cover problemminimum vertex coversuper nodemaximal match

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

Hierarchically specified unit disk graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating linear programming is log-space complete for P
• Efficient solutions of hierarchical systems of linear equations
• The complexity of combinatorial problems with succinct input representation
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Succinct representations of graphs
• Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
• A fast parallel algorithm for the maximal independent set problem
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Parallel Complexity of the Connected Subgraph Problem
• On the Approximation of Maximum Satisfiability
• Hierarchical planarity testing algorithms
• Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions

This page was built for publication: The complexity of approximating PSPACE-complete problems for hierarchical specifications