Graph properties checkable in linear time in the number of vertices
From MaRDI portal
Publication:596315
DOI10.1016/j.jcss.2003.09.002zbMath1069.68079MaRDI QIDQ596315
Etienne Grandjean, Frédéric Olive
Publication date: 10 August 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2003.09.002
problems; Nondeterminism; Combinatorial; Complexity lower bounds; Existential second-order logic; Finite model theory; Linear time
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q19: Descriptive complexity and finite models
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complete problems for monotone NP
- First-order spectra with one variable
- The polynomial-time hierarchy
- Monadic logical definability of nondeterministic linear time
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Invariance properties of RAMs and linear time
- A hierarchy for nondeterministic time complexity
- Time-space tradeoffs for satisfiability
- Computational complexity via programming languages: Constant factors do matter
- Sorting, linear time and the satisfiability problem
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- The Spectra of First-Order Sentences and Computational Complexity
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- A Nontrivial Lower Bound for an NP Problem on Automata
- Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
- Universal quantifiers and time complexity of random access machines
- Languages that Capture Complexity Classes
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Complexity classes and theories of finite models
- A spectrum hierarchy
- On completeness for NP via projection translations
- Linear Time Algorithms and NP-Complete Problems
- Logical Description of Monotone NP Problems
- Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
- Algebraic and logical characterizations of deterministic linear time classes