Structural parameterizations of budgeted graph coloring

DOI10.1016/J.TCS.2022.11.002MaRDI QIDQ5925707zbMATH OpenOpenAlexFDO

Authors Susobhan Bandopadhyay, Suman Banerjee, Aritra Banik, Venkatesh Raman

Publication date 20 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.11.002

zbMATH Keywords

exact exponential algorithmgraph coloringparameterized complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Structural parameterizations of budgeted graph coloring
• Structural parameterizations for equitable coloring
• Budgeted colored matching problems
• \(b\)-coloring parameterized by clique-width
• Parameterized complexity of vertex colouring

Cites work

• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A fast branching algorithm for cluster vertex deletion
• Equitable coloring of trees
• Exact exponential algorithms.
• Fundamentals of parameterized complexity
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Mutual exclusion scheduling
• On the complexity of some colorful problems parameterized by treewidth
• Parameterized algorithms
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Parameterized pre-coloring extension and list coloring problems
• Structural parameterizations for equitable coloring
• Structural parameterizations of budgeted graph coloring

Cited in

(1)

• Budgeted colored matching problems

This page was built for publication: Structural parameterizations of budgeted graph coloring

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