For a graph G = (V, E), a set D subset of V is called a disjunctive dominating set of G if for every vertex v is an element of V \ D, v is either adjacent to a vertex of D or has at least two vertices in D at distance...
详细信息
ISBN:
(纸本)9783319213989;9783319213972
For a graph G = (V, E), a set D subset of V is called a disjunctive dominating set of G if for every vertex v is an element of V \ D, v is either adjacent to a vertex of D or has at least two vertices in D at distance 2 from it. The cardinality of a minimum disjunctive dominating set of G is called the disjunctive domination number of graph G, and is denoted by gamma(d)(2)(G). The MINIMUM DISJUNCTIVE DOMINATION PROBLEM (MDDP) is to find a disjunctive dominating set of cardinality gamma(d)(2)(G). Given a positive integer k and a graph G, the DISJUNCTIVE DOMINATION DECISION PROBLEM (DDDP) is to decide whether G has a disjunctive dominating set of cardinality at most k. In this article, we first propose a polynomial time algorithm for MDDP in proper interval graphs. Next we tighten the NP-completeness of DDDP by showing that it remains NP-complete even in chordal graphs. We also propose a (ln(Delta 2 + Delta + 2) + 1)-approximation algorithm for MDDP, where Delta is the maximum degree of input graph G = (V, E) and prove that MDDP can not be approximated within (1 - epsilon) ln(vertical bar V vertical bar) for any epsilon > 0 unless NP subset of DTIME(vertical bar V vertical bar(O (log log vertical bar V vertical bar))). Finally, we show that MDDP is APX-complete for bipartite graphs with maximum degree 3.
For an integer k >= 0, suppose that each vertex v of a graph G has a set C(v) subset of {0, 1,..., k} of labels, called a list of v. A list L(2, 1)-labeling of G is an assignment of a label in C(v) to each vertex v...
详细信息
For an integer k >= 0, suppose that each vertex v of a graph G has a set C(v) subset of {0, 1,..., k} of labels, called a list of v. A list L(2, 1)-labeling of G is an assignment of a label in C(v) to each vertex v of G such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L(2, 1)-labeling of a graph into another list L(2, 1)-labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L(2, 1)-labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k >= 6. In contrast, we then show that the problem can be solved in linear time for general graphs if k <= 4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L(2, 1)-labelings of a tree can be transformed into each other. (C) 2014 Elsevier B.V. All rights reserved.
This paper investigates how Felzenszwalb's and Huttenlocher's graph-based segmentation algorithm can be improved by automatic programming. We show that computers running Automatic Design of algorithms Through ...
详细信息
ISBN:
(纸本)9783662455234;9783662455227
This paper investigates how Felzenszwalb's and Huttenlocher's graph-based segmentation algorithm can be improved by automatic programming. We show that computers running Automatic Design of algorithms Through Evolution (ADATE), our system for automatic programming, have induced a new graph-based algorithm that is 12 percent more accurate than the original without affecting the runtime efficiency. The result shows that ADATE is capable of improving an effective image segmentation algorithm and suggests that the system can be used to improve image analysis algorithms in general.
By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is origin...
详细信息
By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA' 11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.
We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of O(kn(m + n log n)) and follows the same process as Yen's dev...
详细信息
We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of O(kn(m + n log n)) and follows the same process as Yen's deviation algorithm, but the candidate paths are computed more efficiently using a node classification technique. We first show that a candidate path can be separated by its deviation node as prefix and suffix. Our algorithm then classifies the nodes as red, yellow, and green. A node on the prefix is assigned a red color, a node that can reach t (the destination node) through a shortest path without visiting a red node is assigned a green color, and all other nodes are assigned a yellow color. We prove that when searching for the suffix of a candidate path, all green nodes can be bypassed, and we only need to apply Dijkstra's algorithm to find an all-yellow-node subpath. Since on average the number of yellow nodes is much smaller than n, the new algorithm has a much lower average-case running time. Experiments on many types of networks demonstrate that the new algorithm performs significantly better than existing exact algorithms that have polynomial worst-case complexity. (C) 2014 Wiley Periodicals, Inc.
This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is ...
详细信息
This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs,and chordal comparability graphs.
A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. The cardinality of a minimum k-path vertex cover is called the k-path vertex cover...
详细信息
A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. The cardinality of a minimum k-path vertex cover is called the k-path vertex cover number of a graph G, denoted by psi(k)(G). It is known that the minimum k-path vertex cover problem (k-PVCP) is NP-hard for all k >= 2. In this paper we consider the weighted version of a k-PVCP (k-WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P-k. This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k-WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k-path vertex cover number of a tree with time complexity O(*** bar V(G)vertical bar) is presented. (C) 2014 Elsevier B.V. All rights reserved.
Finding k shortest simple paths in a directed graph is a fundamental problem in many engineering applications. Most existing algorithms such as Yen's algorithm and its variants have polynomial worst-case time comp...
详细信息
Finding k shortest simple paths in a directed graph is a fundamental problem in many engineering applications. Most existing algorithms such as Yen's algorithm and its variants have polynomial worst-case time complexity, but their average-case running time is very high. The heuristic algorithm MPS can run significantly faster in practice. However, it requires an excessive amount of memory space. In this paper, we provide a new heuristic algorithm that achieves high space efficiency while maintaining similar average-case running time. We first propose a sidetrack representation of path, with which a path can be stored in O(1) space. We then show how to categorize a candidate path as either partial or complete, and restrict the number of paths added to the queue. In addition, we provide an empirical equation that can very accurately predict the kth shortest path length, provided that a much smaller number of shortest paths have been found. Extensive experiments prove that our algorithm can achieve an O(n) speedup in practice over Yen's algorithm. In comparison with MPS, it runs up to three times faster and uses less space by an order of magnitude.
Subgraph listing is a fundamental operation to many graph and network analyses. The problem itself is computationally expensive and is well-studied in centralized processing algorithms. However, the centralized soluti...
详细信息
ISBN:
(纸本)9781450323765
Subgraph listing is a fundamental operation to many graph and network analyses. The problem itself is computationally expensive and is well-studied in centralized processing algorithms. However, the centralized solutions cannot scale well to large graphs. Recently, several parallel approaches are introduced to handle the large graphs. Unfortunately, these parallel approaches still rely on the expensive join operations, thus cannot achieve high performance. In this paper, we design a novel parallel subgraph listing framework, named PSgL. The PSgL iteratively enumerates subgraph instances and solves the subgraph listing in a divide-and-conquer fashion. The framework completely relies on the graph traversal, and avoids the explicit join operation. Moreover, in order to improve its performance, we propose several solutions to balance the workload and reduce the size of intermediate results. Specially, we prove the problem of partial subgraph instance distribution for workload balance is NP-hard, and carefully design a set of heuristic strategies. To further reduce the enormous intermediate results, we introduce three independent mechanisms, which are automorphism breaking of the pattern graph, initial pattern vertex selection based on a cost model, and a pruning method based on a light-weight index. We have implemented the prototype of PSgL, and run comprehensive experiments of various graph listing operations on diverse large graphs. The experiments clearly demonstrate that PSgL is robust and can achieve performance gain over the state-of-the-art solutions up to 90%.
暂无评论