Constrained domatic bipartition on trees

DOI10.1016/j.disopt.2016.10.003zbMath1387.05175OpenAlexW2555313947MaRDI QIDQ1751203

Giovanni Andreatta, Luigi De Giovanni, Carla de Francesco, Paolo Serafini

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.10.003

zbMATH Keywords

treepolynomial-time algorithmdominating setcardinality constraintintegral polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Constrained domatic bipartition on trees ⋮ Star partitions on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal shift partitioning of pharmacies
• A linear algorithm for the domination number of a tree
• The domatic number problem
• Constrained domatic bipartition on trees
• Optimal shift coloring of trees
• Domatic Partition on Several Classes of Graphs
• Towards a theory of domination in graphs
• Finding a Domatic Partition of an Interval Graph in Time $O(n)$
• Reducibility among Combinatorial Problems

This page was built for publication: Constrained domatic bipartition on trees