Paired-Domination Problem on Distance-Hereditary Graphs
- PDF / 8,162,295 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 205 Views
Paired‑Domination Problem on Distance‑Hereditary Graphs Ching‑Chi Lin1 · Keng‑Chu Ku2 · Chan‑Hung Hsu2 Received: 16 July 2019 / Accepted: 26 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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(n2 )-time algorithm on distance-hereditary graphs. Keywords Paired-domination · Perfect matching · Distance-hereditary graphs · NP-complete
1 Introduction For a graph G = (V, E) , a vertex subset S ⊆ V(G) is said to be a dominating set of G if every vertex not in S is adjacent to at least a vertex in S. The domination problem involves finding a minimum dominating set of a graph G, which has been received great attention and intensively studied by researchers [11, 12, 33, 34, 36, 37, 42, 43]. Since the domination problem is NP-complete on general graphs [30], many attempts have been made in designing approximation algorithms [3, 39, 44], proving A preliminary version of this work was presented at ICS 2018. * Ching‑Chi Lin [email protected] Keng‑Chu Ku [email protected] Chan‑Hung Hsu [email protected] 1
Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung 20224, Taiwan
2
Department of Computer Science and Information Engineering, National Taiwan University, Taipei 10617, Taiwan
13
Vol.:(0123456789)
Algorithmica Table 1 Results on variants of domination problem on special classes of graphs Graph class
Domination
Paired
Independent
Connected
Total
Bipartite
NPC [5]
NPC [18]
NPC [22]
NPC [52]
NPC [52]
Chordal
NPC [7]
NPC [18]
O(n + m) [26]
NPC [48]
NPC [49]
Split
NPC [5, 22]
NPC [18]
O(n + m) [26]
NPC [48]
NPC [48]
Strongly chordal
O(n + m) [27]
O(n + m) [17]
O(n + m) [26]
O(n + m) [54]
O(n + m) [10]
Interval
O(n + m) [7]
O(n + m) [18]
O(n + m) [26]
O(n + m) [54]
O(n + m) [45]
Circular-arc
O(n + m) [42]
O(n + m) [50]
O(n + m) [12]
O(n + m) [12]
O(n + m) [12]
Circle
NPC [46]
unknown
unknown
NPC [46]
NPC [46]
Permutation
O(n) [15, 28]
O(n) [19, 47]
O(n2 ) [8, 28]
O(n2 ) [8, 21]
O(n4 ) [8, 23]
Distance-hereditary
O(n + m) [14]
O(n2 )a
O(n + m) [41]
O(n + m) [55]
O(n + m) [14]
Tree
O(n) [20]
O(n) [53]
O(n) [6]
O(n) [2]
O(n) [49]
The main result of this paper
General Bipartite
Chordal
Permutation
Split Strongly chordal Interval
Circle
Tree
Distance-hereditary
Circular-arc
Fig. 1 The inclusion relationship between graph classes
NP-completeness and providing polynomial-time algorithms on special classes of graphs [5, 7, 9, 22, 27, 29, 31]. Furthermore, many variations of the domination problem ha
Data Loading...
