On the Descriptive Complexity of Color Coding

DOI10.4230/LIPIcs.STACS.2019.11zbMath1502.68204arXiv1901.03364OpenAlexW2962731244MaRDI QIDQ5090457

Max Bannach, Till Tantau

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1901.03364

zbMATH Keywords

quantifier eliminationfixed-parameter tractabilitydescriptive complexitycolor coding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Descriptive complexity and finite models (68Q19) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Parameterized Parallel Computing and First-Order Logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithm engineering for color-coding with applications to signaling pathway detection
• On the parallel parameterized complexity of the graph isomorphism problem
• Describing parameterized complexity classes
• Parametrized complexity theory.
• The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space
• Computing Hitting Set Kernels By AC^0-Circuits
• Color-coding
• Parallel Multivariate Meta-Theorems
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• Tree-depth, quantifier elimination, and quantifier rank
• Parameterized circuit complexity of model-checking on sparse structures

This page was built for publication: On the Descriptive Complexity of Color Coding