Paired-Domination Problem on Distance-Hereditary Graphs

Autor:	Keng-Chu Ku, Ching-Chi Lin, Chan-Hung Hsu
Rok vydání:	2020
Předmět:	Combinatorics Set (abstract data type) General Computer Science Dominating set Applied Mathematics Theory of computation NP-complete Graph Computer Science Applications Mathematics
Zdroj:	Algorithmica. 82:2809-2840
ISSN:	1432-0541 0178-4617
DOI:	10.1007/s00453-020-00705-7
Popis:	A paired-dominating set of a graph G is a dominating set S of G such that the subgraph of G induced by S has a perfect matching. Haynes and Slater (Networks 32(3):199–206, 1998) introduced the concept of paired-domination and showed that the problem of determining minimum paired-dominating sets is NP-complete on general graphs. Ever since then many algorithmic results are studied on some important classes of graphs. In this paper, we extend the results by providing an $$O(n^2)$$ -time algorithm on distance-hereditary graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::874bf5497d8a6a11b85078cfe2e148fa https://doi.org/10.1007/s00453-020-00705-7 Zobrazit plný text záznamu Full text from SpringerLink