A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O(1.7159(n)) minimal dom...
详细信息
A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O(1.7159(n)) minimal dominating sets. In this paper, we establish upper bounds on this maximum number of minimal dominating sets for split graphs, cobipartite graphs and interval graphs. For each of these graph classes, we provide an algorithm to enumerate them. For split and interval graphs, we show that the number of minimal dominating sets is at most 3(n/3) approximate to 1.4423(n), which is the best possible bound. This settles a conjecture by Couturier et al. (SOFSEM 2012, [11). For cobipartite graphs, we lower the O(1.5875(n)) upper bound from Couturier et al. to O(1.4511(n)). (C) 2014 Elsevier B.V. All rights reserved.
作者：
Inoue, YumaMinato, Shin-ichiHokkaido Univ
Grad Sch Informat Sci & Technol Sapporo Hokkaido Japan JST
ERATO MINATO Discrete Struct Manipulat Syst Project Sapporo Hokkaido Japan
Topological orders of a directed graph are an important concept of graph algorithms. The generation of topological orders is useful for designing graph algorithms and solving scheduling problems. In this paper, we gen...
详细信息
ISBN:
(纸本)9783319130750;9783319130743
Topological orders of a directed graph are an important concept of graph algorithms. The generation of topological orders is useful for designing graph algorithms and solving scheduling problems. In this paper, we generate and index all topological orders of a given graph. Since topological orders are permutations of vertices, we can use the data structure pi DD, which generates and indexes a set of permutations. In this paper, we propose Rot-pi DDs, which are a variation of pi DDs based on a different interpretation. Compression ratios of Rot-pi DDs for representing topological orders are theoretically improved from the original pi DDs. We propose an efficient method for constructing a Rot-pi DD based on dynamic programming approach. Computational experiments show the amazing efficiencies of a Rot-pi DD: a Rot-pi DD for 3.7 x 10(41) topological orders has only 2.2 x 10(7) nodes and is constructed in 36 seconds. In addition, the indexed structure of a Rot-pi DD allows us to fast post-process operations such as edge addition and random samplings.
暂无评论