A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
| creativeworkseries.issn | 1232-9274 | |
| dc.contributor.author | Ziemann, Radosław | |
| dc.contributor.author | Żyliński, Paweł | |
| dc.date.issued | 2025 | |
| dc.description.abstract | We provide a linear time algorithm for determining the sets of vertices that belong to all, some and no minimum dominating sets of a tree, respectively, thus improving the quadratic time algorithm of Benecke and Mynhardt in 2008 [S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209]. Some algorithmic consequences are also discussed. | en |
| dc.description.placeOfPublication | Kraków | |
| dc.description.version | wersja wydawnicza | |
| dc.identifier.doi | https://doi.org/10.7494/OpMath.2025.45.6.841 | |
| dc.identifier.eissn | 2300-6919 | |
| dc.identifier.issn | 1232-9274 | |
| dc.identifier.uri | https://repo.agh.edu.pl/handle/AGH/115660 | |
| dc.language.iso | eng | |
| dc.publisher | Wydawnictwa AGH | |
| dc.relation.ispartof | Opuscula Mathematica | |
| dc.rights | Attribution 4.0 International | |
| dc.rights.access | otwarty dostęp | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/legalcode | |
| dc.subject | tree | en |
| dc.subject | domination | en |
| dc.subject | independence | en |
| dc.subject | vertex cover | en |
| dc.subject | dissociation | en |
| dc.subject | algorithm | en |
| dc.subject | linear time | en |
| dc.subject | dynamic programming | en |
| dc.title | A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences | pl |
| dc.type | artykuł | |
| dspace.entity.type | Publication | |
| publicationissue.issueNumber | No. 6 | |
| publicationissue.pagination | pp. 841-855 | |
| publicationvolume.volumeNumber | Vol. 45 | |
| relation.isJournalIssueOfPublication | 650b1217-dbea-47b4-b371-f5a3d6da1f22 | |
| relation.isJournalIssueOfPublication.latestForDiscovery | 650b1217-dbea-47b4-b371-f5a3d6da1f22 | |
| relation.isJournalOfPublication | 304b3b9b-59b9-4830-9178-93a77e6afbc7 |