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.
Keywords
Cite this article
@article{cai-1613-2008-4,
author = {Ľudovít Niepel and Anton Černý},
title = {Independence and Domination in Path Graphs of Trees},
journal = {Computing and Informatics},
volume = {27},
number = {4},
pages = {581--591},
year = {2008},
issn = {1335-9150},
url = {https://cai.type.sk/content/2008/4/independence-and-domination-in-path-graphs-of-trees/}
}
TY - JOUR AU - Ľudovít Niepel AU - Anton Černý TI - Independence and Domination in Path Graphs of Trees JO - Computing and Informatics VL - 27 IS - 4 SP - 581 EP - 591 PY - 2008 SN - 1335-9150 UR - https://cai.type.sk/content/2008/4/independence-and-domination-in-path-graphs-of-trees/ KW - Path graph KW - dominating set KW - independent set ER -
Niepel, Ľ., & Černý, A. (2008). Independence and Domination in Path Graphs of Trees. Computing and Informatics, 27(4), 581–591. https://cai.type.sk/content/2008/4/independence-and-domination-in-path-graphs-of-trees/