Strong elimination ordering of the total graph of a tree

Strong elimination ordering of the total graph of a tree

0.00 Avg rating0 Votes
Article ID: iaor19931473
Country: Netherlands
Volume: 39
Issue: 3
Start Page Number: 293
End Page Number: 295
Publication Date: Nov 1992
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: computational analysis
Abstract:

Total graphs of trees were proved strongly chordal by Martin Farber. The authors give a new proof of this fact by directly constructing a strong elimination ordering. The present method can be implemented to run in linear time. As an application, the authors give a new linear algorithm for the minimum weight total dominating set problem for trees.

Reviews

Required fields are marked *. Your email address will not be published.