Independence and Domination in Path Graphs of Trees
Keywords:
Path graph, dominating set, independent setAbstract
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 http://147.213.75.17/ojs/index.php/cai/article/view/233
Issue
Section
Articles