Graph properties checkable in linear time in the number of vertices

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

zbMATH Keywords

problemsNondeterminismCombinatorialComplexity lower boundsExistential second-order logicFinite model theoryLinear time

Mathematics Subject Classification ID

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