In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP complete even when restricted to bipartite...
详细信息
In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP complete even when restricted to bipartite graphs. It has been proved that MATCHING CUT is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d >= 3, MATCHING CUT is NP-complete in the class of graphs of diameter d. This resolves an open problem posed by Borowiecki and Jesse-Jozefczyk (2008) [6]. We then show that, for any fixed integer d >= 4, MATCHING CUT is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that MATCHING CUT is polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving MATCHING CUT in graphs of diameter 2. (C) 2018 Elsevier B.V. All rights reserved.
For a graph G = (V, E), a set D subset of V is called a semitotal dominating set of G if D is a dominating set of G, and every vertex in D is within distance 2 of another vertex of D. The MINIMUM SEMITOTAL DOMINATION ...
详细信息
For a graph G = (V, E), a set D subset of V is called a semitotal dominating set of G if D is a dominating set of G, and every vertex in D is within distance 2 of another vertex of D. The MINIMUM SEMITOTAL DOMINATION problem is to find a semitotal dominating set of minimum cardinality. Given a graph G and a positive integer k, the SEMITOTAL DOMINATION DECISION problem is to decide whether G has a semitotal dominating set of cardinality at most k. The SEMITOTAL DOMINATION DECISION problem is known to be NP-complete for general graphs. In this paper, we show that the SEMITOTAL DOMINATION DECISION problem remains NP-complete for planar graphs, split graphs and chordal bipartite graphs. We give a polynomial time algorithm to solve the MINIMUM SEMITOTAL DOMINATION problem in interval graphs. We show that the MINIMUM SEMITOTAL DOMINATION problem in a graph with maximum degree A admits an approximation algorithm that achieves the approximation ratio of 2+3ln(Delta+1), showing that the problem is in the class log-APX. We also show that the MINIMUM SEMITOTAL DOMINATION problem cannot 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(0(log log vertical bar v vertical bar))) Finally, we prove that the MINIMUM SEMITOTAL DOMINATION problem is APX-complete for bipartite graphs with maximum degree 4. (C) 2018 Elsevier B.V. All rights reserved.
A (d, n)-packing k-coloring of a graph G for integers d and n is a mapping from V(G) to the set {1, 2, ..., k} such that vertices with color i is an element of {1, 2, ..., k} have pairwise distance greater than d + le...
详细信息
A (d, n)-packing k-coloring of a graph G for integers d and n is a mapping from V(G) to the set {1, 2, ..., k} such that vertices with color i is an element of {1, 2, ..., k} have pairwise distance greater than d + left perpendicular i-1/n right perpendicular The smallest integer k for which there exists a (d, n)-packing coloring of a graph G is called the (d, n)-packing chromatic number of G. We propose a new heuristic approach to find (d, n)-packing colorings of infinite lattices. The proposed algorithms have been able to obtain several (d, n)-packing colorings of the infinite square, hexagonal, triangular, eight-regular and octagonal lattice. The obtained results improve upper bounds on the corresponding (d, n)-packing chromatic numbers for these graphs. (C) 2018 Published by Elsevier B.V.
A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (called a reconfiguration sequence) ...
详细信息
A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (called a reconfiguration sequence) between two c-colorable sets in the same graph. This problem generalizes the well-studied INDEPENDENT SET RECONFIGURATION problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for FEEDBACK VERTEX SET RECONFIGURATION. (C) 2018 Elsevier B.V. All rights reserved.
A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex u is not an element of S, there is a vertex v is an element of S such that uv is an edge and (S \ ...
详细信息
A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex u is not an element of S, there is a vertex v is an element of S such that uv is an edge and (S \ {v}) boolean OR {u} is also a dominating set of G. The secure domination number gamma(s)(G) is the cardinality of a smallest secure dominating set of G. In this paper, we propose a linear-time algorithm for finding the secure domination number of cographs. (C) 2019 Elsevier B.V. All rights reserved.
In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph G with the integer l...
详细信息
In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph G with the integer lattice, seen as a graph, in such a way that the resulting hypothetical graph can be traversed using a known algorithm which is based on face routing. To overcome the problem with hypothetical vertices and edges, we develop an algorithm for visiting any k-th neighborhood of a vertex in a graph straight-line drawn in the plane using O(k log k) memory. The memory needed to complete the traversal of a geometric graph then turns out to depend on the maximum graph distance among pairs of distinct vertices of G whose Euclidean distance is greater than one and less than 2 root 2.
A safe set of a graph is a non-empty subset S of V such that for every component A of G[S] and every component B of , we have whenever there exists an edge of G between A and B. In this paper, we show that a minimum s...
详细信息
A safe set of a graph is a non-empty subset S of V such that for every component A of G[S] and every component B of , we have whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.
The dispersion problem on graphs requires k robots placed arbitrarily at the n nodes of an anonymous graph, where k <= n, to coordinate with each other to reach a final configuration in which each robot is at a dis...
详细信息
ISBN:
(纸本)9781450360944
The dispersion problem on graphs requires k robots placed arbitrarily at the n nodes of an anonymous graph, where k <= n, to coordinate with each other to reach a final configuration in which each robot is at a distinct node of the graph. The dispersion problem is important due to its relationship to graph exploration by mobile robots, scattering on a graph, and load balancing on a graph. In addition, an intrinsic application of dispersion has been shown to be the relocation of self-driven electric cars (robots) to recharge stations (nodes). We propose five algorithms to solve dispersion on graphs. The first three algorithms require O(k log Delta) bits at each robot andO(m) steps running time, wherem is the number of edges and Delta is the degree of the graph. The algorithms differ in whether they address the synchronous or the asynchronous system model, and in what, where, and how data structures are maintained. The fourth algorithm, for the asynchronous model, has a space usage of O(D log Delta) bits at each robot and uses O(Delta(D)) steps, where D is the graph diameter. The fifth algorithm, for the asynchronous model, has a space usage of O(max(log k, log Delta)) bits at each robot and uses O((m - n) k) steps.
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 (GPUs) have become popular high-performance computing platforms for a wide range of applications. The trend of processing graph structures on modern GPUs has also attracted an increasing inte...
详细信息
graphics processing units (GPUs) have become popular high-performance computing platforms for a wide range of applications. The trend of processing graph structures on modern GPUs has also attracted an increasing interest in recent years. This article aims to review research works on adapting the massively parallel architecture of GPUs to accelerate the performance of fundamental graph operations. Despite their merits, some factors such as the unique architecture of GPUs, limited programming models, and irregular structures of graphs prevent GPU implementations from achieving high performance. Thus, this survey also discusses challenges and optimization techniques used by recent studies to fully utilize the GPU capability. A categorization of the existing research works is also presented based on the specific issues these attempted to solve.
暂无评论