Independence and Domination in Path Graphs of Trees
Ľudovít Niepel ; Anton Černý
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  Path graph; dominating set; independent set 
@article{cai233,
     author = {\v Ludov\'\i t Niepel and Anton \v Cern\'y},
     title = {Independence and Domination in Path Graphs of Trees},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai233}
}

Ľudovít Niepel; Anton Černý. Independence and Domination in Path Graphs of Trees. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai233/