Graph properties checkable in linear time in the number of vertices
From MaRDI portal
Publication:596315
DOI10.1016/j.jcss.2003.09.002zbMath1069.68079OpenAlexW2142482847MaRDI 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
problemsNondeterminismCombinatorialComplexity lower boundsExistential second-order logicFinite model theoryLinear time
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Descriptive complexity and finite models (68Q19)
Related Items (9)
A logical approach to locality in pictures languages ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ Descriptive complexity of \#P functions: a new perspective ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Unnamed Item ⋮ Expressivity and Complexity of Dependence Logic ⋮ Unnamed Item ⋮ Existential second-order logic and modal logic with quantified accessibility relations
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
This page was built for publication: Graph properties checkable in linear time in the number of vertices
