Parameterized complexity of satisfactory partition problem

DOI10.1016/J.TCS.2022.01.022MaRDI QIDQ5918491zbMATH OpenOpenAlexFDO

Authors Ajinkya Gaikwad, Soumen Maity, Shuvam Kant Tripathi

Publication date 21 February 2022

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

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

zbMATH Keywords

treewidthclique-widthparameterized complexityFPTneighbourhood diversityw[1-hard]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Parameterized complexity of satisfactory partition problem
• The balanced satisfactory partition problem
• Computing and Combinatorics
• The satisfactory partition problem
• Satisfactory graph partition, variants, and generalizations

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2104729 (Why is no real title available?)
• Algorithmic approach to the satisfactory graph partitioning problem
• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms and Computation
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Alliances in graphs of bounded clique-width
• Computing and Combinatorics
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• Graph minors. III. Planar tree-width
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Parameterized algorithms
• Parameterized complexity of satisfactory partition problem
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• The satisfactory partition problem

Cited in

(5)

• Proportionally dense subgraphs: parameterized hardness and efficiently solvable cases
• The unbiased black-box complexity of partition is polynomial
• Parameterized complexity of satisfactory partition problem
• Finding \(k\)-community structures in special graph classes
• Finding proportionally dense subgraphs of maximum size in degree-constrained graphs

This page was built for publication: Parameterized complexity of satisfactory partition problem

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