Independence and Domination in Path Graphs of Trees

In: Computing and Informatics, vol. 27, no. 4

Ľ. Niepel - A. Černý

Details:

Year, pages: 2008, 581 - 591

Keywords:

Path graph, dominating set, independent set

About article:

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.

How to cite:

ISO 690:

Niepel, Ľ., Černý, A. 2008. Independence and Domination in Path Graphs of Trees. In Computing and Informatics, vol. 27, no.4, pp. 581-591. 1335-9150.

APA:

Niepel, Ľ., Černý, A. (2008). Independence and Domination in Path Graphs of Trees. Computing and Informatics, 27(4), 581-591. 1335-9150.