Independence and Domination in Path Graphs of Trees

Ľudovít Niepel; Anton Černý

Independence and Domination in Path Graphs of Trees

Authors

Ľudovít Niepel
Anton Černý

Keywords:

Path graph, dominating set, independent set

Abstract

The problems of determining the maximum cardinality of an independent set of vertices and the minimum cardinality of a maximal independent set of vertices of a graph are known to be NP-complete. We provide efficient algorithms for finding these values for path graphs of trees.

Downloads

Download data is not yet available.

Downloads

Published

2012-01-26

How to Cite

Niepel, Ľudovít, & Černý, A. (2012). Independence and Domination in Path Graphs of Trees. COMPUTING AND INFORMATICS, 27(4), 581–591. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/233