Parameterized complexity of modular dominating structures in bounded-treewidth graphs

DOI10.61091/UM126-12MaRDI QIDQ7227498zbMATH OpenFDO

Authors Dhilshath Shajahan

Publication date 10 April 2026

Published in Utilitas Mathematica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.61091/UM126-12

zbMATH Keywords

graph algorithmsparameterized complexitytree decompositionmodular constraints\((\sigma, \rho)\)-dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A dichotomy theorem for nonuniform CSPs
• A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Exact algorithms for maximum independent set
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Independent sets with domination constraints
• Lower bounds based on the exponential time hypothesis
• Parameterized algorithms
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?

This page was built for publication: Parameterized complexity of modular dominating structures in bounded-treewidth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7227498)