A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set...
详细信息
ISBN:
(纸本)9783031343469;9783031343476
A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set of size (1.9091OPT + 6) on 2-connected AT-free graphs with running time O(n(8)m(2)). Also, we give another approximation algorithm that computes a connected feedback vertex set of size (2.9091OPT + 6) on the same graph class with more efficient running time O(min{m(log(n)), n(2)}).
This paper is motivated by the problem of subdividing a prismatic mesh to a tetrahedral mesh with prescribed boundary conditions and without inserting Steiner points. We show that this 3D subdivision problem can be mo...
详细信息
ISBN:
(纸本)9783319099941;9783319099934
This paper is motivated by the problem of subdividing a prismatic mesh to a tetrahedral mesh with prescribed boundary conditions and without inserting Steiner points. We show that this 3D subdivision problem can be modeled as a 2D cutting flow problem. Then we propose a complete solution to the cutting flow problem, covering all possible combinations of base domain topology and boundary condition. We not only provide provable sufficient and necessary conditions for existence of solutions, but also provide linear algorithms to compute a solution whenever there is one.
We study the problem to find a partition of a graph G with maximum social welfare based on social distance between vertices in G, called MaxSWP. This problem is known to be NP-hard in general. In this paper, we first ...
详细信息
ISBN:
(纸本)9783030105648;9783030105631
We study the problem to find a partition of a graph G with maximum social welfare based on social distance between vertices in G, called MaxSWP. This problem is known to be NP-hard in general. In this paper, we first give a complete characterization of optimal partitions of trees with small diameters. Then, by utilizing these results, we show that MaxSWP can be solved in linear time for trees. Moreover, we show that MaxSWP is NP-hard even for 4-regular graphs.
graphics Processing Units (GPU) are application specific accelerators which provide high performance to cost ratio and are widely available and used, hence places them as a ubiquitous accelerator. A computing paradigm...
详细信息
graphics Processing Units (GPU) are application specific accelerators which provide high performance to cost ratio and are widely available and used, hence places them as a ubiquitous accelerator. A computing paradigm based on the same is the general purpose computing on the GPU (GPGPU) model. The GPU due to its graphics lineage is better suited for the data-parallel, data-regular algorithms. The hardware architecture of the GPU is not suitable for the data parallel but data irregular algorithms such as graph connected components and list ranking. In this paper, we present results that show how to use GPUs efficiently for graph algorithms which are known to have irregular data access *** consider two fundamental graph problems: finding the connected components and finding a spanning tree. These two problems find applications in several graph theoretical problems. In this paper we arrive at efficient GPU implementations for the above two problems. The algorithms focus on minimising irregularity at both algorithmic and implementation level. Our implementation achieves a speedup of 11-16 times over a corresponding best sequential implementation.
Let G = (V, E) be a connected graph with at least two vertices. For a fixed positive integer b > 1, a set D subset of V is called a b-disjunctive total dominating set of G if for every vertex v is an element of V, ...
详细信息
ISBN:
(纸本)9783319292212;9783319292205
Let G = (V, E) be a connected graph with at least two vertices. For a fixed positive integer b > 1, a set D subset of V is called a b-disjunctive total dominating set of G if for every vertex v is an element of V, v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The minimum cardinality of a b-disjunctive total dominating set of G is called the b-disjunctive total domination number of G, and is denoted by gamma(td)(b) (G). The MINIMUM b-DISJ TOTAL DOMINATION problem is to find a b-disjunctive total dominating set of cardinality gamma(td)(b) (G). Given a positive integer k and a graph G, the b-DISJ TOTAL DOM DECISION problem is to decide whether G has a b-disjunctive total dominating set of cardinality at most k. In this paper, we initiate the algorithmic study of the Minimum b-DISJ TOTAL DOMINATION PROBLEM. We prove that the b-DISJ TOTAL DOM DECISION PROBLEM is NP-complete even for bipartite graphs and chordal graphs, two important graph classes. On the positive side, we propose a ln(Delta(2) + (b-1)Delta) + 1-approximation algorithm for the MINIMUM b-DISJ TOTAL DOMINATION PROBLEM. We prove that the Minimum b-DISJ TOTAL DOMINATION problem cannot be approximated within 1/2 (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 the MINIMUM b-DISJ TOTAL DOMINATION problem is APX-complete for bipartite graphs with maximum degree b + 3.
In the paper, we describe the Wiki GRAPP and WEGA systems intended to help in leaching and research in graph theory, graph algorithms and their applications to computer science.
ISBN:
(纸本)9781605588209
In the paper, we describe the Wiki GRAPP and WEGA systems intended to help in leaching and research in graph theory, graph algorithms and their applications to computer science.
The single maximum coverage location problem is as follows. We are given an edge-weighted tree with customers located at the nodes. Each node u is associated with a demand w(u) and a radius r(u). The goal is to find, ...
详细信息
ISBN:
(纸本)9783642175169
The single maximum coverage location problem is as follows. We are given an edge-weighted tree with customers located at the nodes. Each node u is associated with a demand w(u) and a radius r(u). The goal is to find, for some facility, a node x such that the total demand of customers u whose distance to x is at most r(u) is maximized. We give a simple O(n log n) algorithm for this problem which improves upon the previously fastest algorithms. We complement this result by an Omega(n log n) lower bound showing that our algorithm is optimal. We observe that our algorithm leads also to improved time bounds for several other location problems such as indirect covering subtree and certain competitive location problems. Finally, we outline how our algorithm can be extended to a large class of distance-based location problems.
The minimum spanning tree problem originated in the 1920s when O. Borůvka identified and solved the problem during the electrification of Moravia. This graph theory problem and its numerous applications have inspired ...
详细信息
Given a graph, an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >= 2 if u an...
详细信息
ISBN:
(纸本)9783030108014;9783030108007
Given a graph, an L(2, 1)-labeling of the graph is an assignment l from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), vertical bar l(u) - l(v)vertical bar >= 2 if u and v are adjacent, and l(u) not equal l(nu) if u and v are at distance 2. The L(2, 1)-labeling problem is to minimize the span of l (i.e., max(u is an element of V) (l(u)) - min(u is an element of V) (l(u)) + 1). In this paper, we propose a new polynomial-time 116/13-approximation algorithm for L(2, 1)-labeling of unit disk graphs. This improves the previously best known ratio 12.
Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs. In this paper...
详细信息
ISBN:
(纸本)9781665420556
Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs. In this paper, we study computationally efficient diffusion primitives beyond random walk. We design an near-linear time randomized algorithm for the 2-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time. From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.
暂无评论