Complexity and approximation of satisfactory partition problems

DOI10.1007/11533719_84MaRDI QIDQ5717006zbMATH OpenOpenAlexFDO

Authors Zsolt Tuza, Daniel Vanderpooten, Cristina Bazgan

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11533719, https://basepub.dauphine.fr/handle/123456789/5906

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• The satisfactory partition problem
• Satisfactory graph partition, variants, and generalizations
• Algorithms and Computation
• The balanced satisfactory partition problem
• Approximation of satisfactory bisection problems

Cited in

(24)

• On the complexity of assembly partitioning
• Algorithmic approach to the satisfactory graph partitioning problem
• Momentopes, the complexity of vector partitioning, and Davenport-Schinzel sequences
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• Computability of width of submodular partition functions
• A note on the satisfactory partition problem: constant size requirement
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• The satisfactory partition problem
• On the complexity of optimal multisplitting
• Simulation as coarsest partition problem
• The unbiased black-box complexity of partition is polynomial
• On the complexity of some quorum colorings problems of graphs
• Stabilization Time in Weighted Minority Processes
• Algorithms and Computation
• A 2-approximation for the maximum satisfying bisection problem
• Relaxed complete partitions: an error-correcting Bachet's problem
• Simplex partitioning via exponential clocks and the multiway cut problem
• Parameterized complexity of satisfactory partition problem
• Parameterized complexity of satisfactory partition problem
• A general stabilization bound for influence propagation in graphs
• The balanced satisfactory partition problem
• Approximation of satisfactory bisection problems
• Satisfactory graph partition, variants, and generalizations

This page was built for publication: Complexity and approximation of satisfactory partition problems

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