Graph properties checkable in linear time in the number of vertices

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

zbMATH Keywords

problems; Nondeterminism; Combinatorial; Complexity lower bounds; Existential second-order logic; Finite model theory; Linear time

Mathematics Subject Classification ID

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