In this paper, we initiate the study of total liar's domination of a graph. A subset LaS dagger V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all vaV, |N (G) (v)a (c) L|a parts p...
详细信息
In this paper, we initiate the study of total liar's domination of a graph. A subset LaS dagger V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all vaV, |N (G) (v)a (c) L|a parts per thousand yen2 and (ii) for every pair u,vaV of distinct vertices, |(N (G) (u)a(a)N (G) (v))a (c) L|a parts per thousand yen3. The total liar's domination number of a graph G is the cardinality of a minimum total liar's dominating set of G and is denoted by gamma (TLR) (G). The Minimum Total Liar's Domination Problem is to find a total liar's dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar's Domination Decision Problem is to check whether G has a total liar's dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar's dominating set in a graph. We show that the Total Liar's Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(ln Delta(G)+1)-approximation algorithm for the Minimum Total Liar's Domination Problem, where Delta(G) is the maximum degree of the input graph G. We show that Minimum Total Liar's Domination Problem cannot be approximated within a factor of for any I mu > 0, unless NPaS dagger DTIME(|V|(loglog|V|)). Finally, we show that Minimum Total Liar's Domination Problem is APX-complete for graphs with bounded degree 4.
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. This paper provides a first bran...
详细信息
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. This paper provides a first branching algorithm solving MATCHING Cur in time O*(2(n/2)) = O*(1.4143(n)) for an n-vertex input graph, and shows that MATCHING CUT parameterized by the vertex cover number tau(G) can be solved by a single-exponential algorithm in time 2 tau((G)) O(n(2)). Moreover, the paper also gives a polynomially solvable case for MATCHING Cur which covers previous known results on graphs of maximum degree three, line graphs, and claw-free graphs. (C) 2015 Elsevier B.V. All rights reserved.
Partitioning the Maximal Redundant Rigid Components (MRRC) and Maximal Global Rigid Components (MGRC) in generic 2D graphs are critical problem for network structure analysis, network localizability detection, and loc...
详细信息
Partitioning the Maximal Redundant Rigid Components (MRRC) and Maximal Global Rigid Components (MGRC) in generic 2D graphs are critical problem for network structure analysis, network localizability detection, and localization algorithm design. This article presents efficient algorithms to partition MRRCs and MGRCs and develops an open-sourced toolbox, GPART, for these algorithms to be conveniently used by the society. We firstly propose conditions and an efficient algorithm to merge the over-constrained regions to form the maximal redundant rigid components (MRRC). The detected MRRCs are proved to be maximal and all the MRRCs are guaranteed to be detected. The time to merge the over-constrained regions is linear to the number of nodes in the over-constrained components. To detect MGRCs, the critical problem is to decompose 3-connected components in each MRRC. We exploit SPQR-tree based method and design a local optimization algorithm, called MGRC_acce to prune the unnecessary decomposition operations so that the SPQR-tree functions can be called much less number of times. We prove the MGRCs can be detected inside MRRCs using at most O(mn) time. Then a GPART toolbox is developed and extensively tested in graphs of different densities. We show the proposed MRRC and MGRC detection algorithms are valid and MGRC_acce greatly outperforms the direct SPQR-tree based decomposition algorithm. GPART is outsourced at https://***/inlab-group/gpart.
A new algorithm is given to find a maximum flow in an undirected planar flow network in $O(n\log ^2 n)$ time, which is faster than the best method previously known by a factor of $\sqrt n /\log n$. The algorithm const...
详细信息
A new algorithm is given to find a maximum flow in an undirected planar flow network in $O(n\log ^2 n)$ time, which is faster than the best method previously known by a factor of $\sqrt n /\log n$. The algorithm constructs a transformation of the dual of the given flow network in which differences between shortest distances are equal, under suitable edge correspondences, to edge flows in the given network. The transformation depends on the value of a maximum flow. The algorithm then solves the shortest distances problem efficiently by exploiting certain structural properties of the transformed dual, as well as using a set of cuts constructible in $O(n\log ^2 n)$ time by a known method which is also used to find the requisite flow value. The main result can be further improved by a factor of $\log n/\log^* n$ if a recently developed shortest path algorithm for planar networks is used in place of Dijkstra’s algorithm in each step where shortest paths are computed.
Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf ...
详细信息
Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K c. V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard for any fixed constant number of terminals with vertical bar K vertical bar >= 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with vertical bar K vertical bar >= 3. Finally, we give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if vertical bar K vertical bar = O(vertical bar V vertical bar), and the hidden constant factor of the running time is just a single exponential of the treewidth.
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.
The problems of recognizing series-parallel graphs, outerplanar graphs, and generalized series-parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the a...
详细信息
The problems of recognizing series-parallel graphs, outerplanar graphs, and generalized series-parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O(|E| + |V |)-time certifying algorithm that simultaneously determines if a graph G = (V, E) is series- parallel, outerplanar, or generalized series-parallel is presented. The positive certificates are a construction sequence for constructing G if G is series-parallel, a generalized construction sequence for constructing G if G is generalized series-parallel but not series-parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components.(c) 2022 Elsevier B.V. All rights reserved.
Suppose that we are given two dominating sets D-s and D-t of a graph G whose cardinalities are at most a given threshold k. Then, we are asked whether there exists a sequence of dominating sets of G between D-s, and D...
详细信息
Suppose that we are given two dominating sets D-s and D-t of a graph G whose cardinalities are at most a given threshold k. Then, we are asked whether there exists a sequence of dominating sets of G between D-s, and Dt such that each dominating set in the sequence is of cardinality at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by O(n), where n is the number of vertices in the input graph. (C) 2016 Elsevier B.V. All rights reserved.
In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D, find a path in D that collects a maximum number of distinct labels. For any epsilon >...
详细信息
In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D, find a path in D that collects a maximum number of distinct labels. For any epsilon > 0, we provide a polynomial time approximation algorithm that computes a solution of value at least OPT1-epsilon and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the APX-hardness of the problem, shows that the problem cannot be approximated within any constant ratio unless P = NP.
The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks ...
详细信息
The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present a 1.1736(n)n(0(1))-time exact algorithm for the maximum independent set problem in an n-vertex graph with degree bounded by 5, improving the previous running time bound of 1.1895(n)n(0(1)). In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论