Linear Time Algorithms and NP-Complete Problems

DOI10.1137/S0097539791223206zbMath0814.68062OpenAlexW2059813129MaRDI QIDQ4302285

Etienne Grandjean

Publication date: 14 August 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539791223206

zbMATH Keywords

complexity theory polynomial

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Algebraic and logical characterizations of deterministic linear time classes ⋮ Graph properties checkable in linear time in the number of vertices ⋮ A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES ⋮ Sorting, linear time and the satisfiability problem ⋮ Exact complexity of problems of incompletely specified automata ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ Linear time and the power of one first-order universal quantifier ⋮ On the expressive power of monadic least fixed point logic

This page was built for publication: Linear Time Algorithms and NP-Complete Problems