2022 · 30 citations · 30 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationDirected Acyclic GraphsGraph AlgorithmsGraph TheoryModel CheckingModel TheoryStructural ComplexityAlgorithmic Graph TheoryComputational Complexity Of Graph AlgorithmsEnumerative AlgorithmsEnumerative Graph TheoryExponential GrowthGraph EnumerationNip TheoriesStructural Properties Of Complexity Classes
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.
30
Frank Plumpton Ramsey · Proceedings of the London Mathematical Society · 1930 · 1.9K citations
Russell Impagliazzo, Ramamohan Paturi · Journal of Computer and System Sciences · 2001 · 1K citations