2018/03/12 by Nina Chiarelli, Tatiana Romina Hartinger, Chiarelli, Nina +7
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1803.04327
openalex publication_date 2018/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a positive integer k, a k-dominating set in a graph G is a set of\nvertices such that every vertex not in the set has at least k neighbors in\nthe set. A total k-dominating set, also known as a k-tuple total dominating\nset, is a set of vertices such that every vertex of the graph has at least k\nneighbors in the set. The problems of finding the minimum size of a\nk-dominating, respectively total k-dominating set, in a given graph, are\nreferred to as k-domination, respectively total k-domination. These\ngeneralizations of the classical domination and total domination problems are\nknown to be NP-hard in the class of chordal graphs, and, more specifically,\neven in the classes of split graphs (both problems) and undirected path graphs\n(in the case of total k-domination). On the other hand, it follows from\nrecent work of Kang et al.~(2017) that these two families of problems are\nsolvable in time \O(|V(G)|6k+4) in the class of interval graphs.\nWe develop faster algorithms for k-domination and total k-domination in the\nclass of proper interval graphs, by means of reduction to a single shortest\npath computation in a derived directed acyclic graph with\n\O(|V(G)|2k) nodes and \O(|V(G)|4k) arcs. We show\nthat a suitable implementation, which avoids constructing all arcs of the\ndigraph, leads to a running time of \O(|V(G)|3k). The algorithms\nare also applicable to the weighted case.\n