Partitioning trees: Matching, domination, and maximum diameter

DOI10.1007/BF00978378zbMath0464.68068OpenAlexW2036862358MaRDI QIDQ3916030

Stephen T. Hedetniemi, Arthur M. Farley, Andrzej Proskurowski

Publication date: 1981

Published in: International Journal of Computer & Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00978378

zbMATH Keywords

efficient algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

An approximation algorithm for clustering graphs with dominating diametral path, A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees, Graph theory (algorithmic, algebraic, and metric problems), Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, Exact algorithms for the minimum \(s\)-club partitioning problem, Combinatorial analysis (nonnegative matrices, algorithmic problems), On some optimization problems on \(k\)-trees and partial \(k\)-trees, Broadcasting in Trees with Multiple Originators, Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• A linear algorithm for the domination number of a tree
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• b-Matchings in Trees
• A Linear Tree Partitioning Algorithm
• Two-Commodity Flow