On the IO-complexity and approximation languages

DOI10.1016/0020-0190(88)90139-1zbMath0659.03023OpenAlexW2062108502MaRDI QIDQ1112018

José D. P. Rolim, Sheila A. Greibach

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90139-1

zbMATH Keywords

IO-complexityapproximation solutionsinfinitely often

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (1)

On the polynomial IO-complexity

Cites Work

• Average time analyses of simplified Davis-Putnam procedures
• A note on the best-case complexity
• Solving low-density subset sum problems
• Determining the Chromatic Number of a Graph
• The NP-completeness column: An ongoing guide

This page was built for publication: On the IO-complexity and approximation languages