A set D subset of V of a graph G = (V, E) is called a connected power dominating set of G if G[D], the subgraph induced by D, is connected and every vertex in the graph can be observed from D, following the two observ...
详细信息
A set D subset of V of a graph G = (V, E) is called a connected power dominating set of G if G[D], the subgraph induced by D, is connected and every vertex in the graph can be observed from D, following the two observation rules for power system monitoring: Rule 1: if v epsilon D, then v can observe itself and all its neighbors, and Rule 2: for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Given a graph G, Minimum Connected Power Domination is to find a connected power dominating set of minimum cardinality of G and Decide Connected Power Domination is the decision version of Minimum Connected Power Domination. Decide Connected Power Domination is known to be NP-complete for general graphs. In this paper, we prove that Decide Connected Power Domination remains NP-complete for star-convex bipartite graphs, perfect elimination bipartite graphs and split graphs. This answers some open problems posed in [B. Brimkov, D. Mikesell and L. Smith, Connected power domination in graphs, J. Comb. Optim. 38(1) (2019) 292{315]. On the positive side, we show that Minimum Connected Power Domination is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination cannot be approximated within (1- epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless P = NP, for bipartite graphs as well as for chordal graphs. Finally, we show that Minimum Connected Power Domination is APX-hard for bounded degree graphs.
We prove a "decomposition lemma" that allows us to count preimages of certain sets of permutations under West's stacksorting map s. As a first application, we give a new proof of Zeilberger's formula...
详细信息
We prove a "decomposition lemma" that allows us to count preimages of certain sets of permutations under West's stacksorting map s. As a first application, we give a new proof of Zeilberger's formula for the number W-2(n) of 2-stack-sortable permutations in S-n. Our proof generalizes, allowing us to find an algebraic equation satisfied by the generating function that counts 2-stack-sortable permutations according to length, number of descents, and number of peaks. This is also the first proof of this formula that generalizes to the setting of 3-stack-sortable permutations. Indeed, the same method allows us to obtain a recurrence relation for W-3(n), the number of 3-stack-sortable permutations in S-n. Hence, we obtain the first polynomial-time algorithm for computing these numbers. We compute W-3(n) for n <= 174, vastly extending the 13 terms of this sequence that were known before. We also prove the first nontrivial lower bound for lim(n ->infinity) W-3(n)(1/n), showing that it is at least 8.659702. Invoking a result of Kremer, we also prove that lim(n ->infinity) W-t(n)(1/n) >= (root t + 1)(2) for all t >= 1, which we use to improve a result of Smith concerning a variant of the stacksorting procedure. Our computations allow us to disprove a conjecture of Bona, although we do not yet know for sure which one. In fact, we can refine our methods to obtain a recurrence for W-3(n, k, p), the number of 3-stack-sortable permutations in S-n with k descents and p peaks. This allows us to gain a large amount of evidence supporting a real-rootedness conjecture of Bona. Using part of the theory of valid hook configurations, we give a new proof of a gamma-nonnegativity result of Branden, which in turn implies an older result of Bona. We then answer a question of the current author by producing a set A subset of S-11 such that Sigma(sigma is an element of s-1)(A)(xdes(sigma)) has nonreal roots. We interpret this as partial evidence against the same real-rootedness conjecture of B
The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is *** is a well-known NP-hard problem in network *** paper studies th...
详细信息
The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is *** is a well-known NP-hard problem in network *** paper studies the fixed-parameter solvability,that is,for a given graph G and an integer k,to decide whether there exists a path P in G such that max v∈V(G)d_(G)(v,P)≤*** the answer is affirmative,then graph G is called *** show that this decision problem is NP-complete even for k=*** the other hand,we characterize the family of 1-path-eccentric graphs,including the traceable,interval,split,permutation graphs and ***,some polynomially solvable special graphs are discussed.
We propose an algorithm for finding zero divisors in quaternion algebras over quadratic number fields, or equivalently, solving homogeneous quadratic equations in three variables over Q(root d) where d is a square-fre...
详细信息
We propose an algorithm for finding zero divisors in quaternion algebras over quadratic number fields, or equivalently, solving homogeneous quadratic equations in three variables over Q(root d) where d is a square-free integer. The algorithm is randomized and runs in polynomialtime if one is allowed to call oracles for factoring integers. (C) 2018 Elsevier Ltd. All rights reserved.
A polynomial-time algorithm is designed for finding an optimal solution of a discrete optimization problem to which a pattern recognition problem is reduced, namely, the noise-proof recognition of a sequence as a stru...
详细信息
A polynomial-time algorithm is designed for finding an optimal solution of a discrete optimization problem to which a pattern recognition problem is reduced, namely, the noise-proof recognition of a sequence as a structure consisting of contiguous subsequences in the form of series of identical nonzero vectors from an alphabet of vectors in the Euclidean space that alternate with zero vectors.
The notion of augmenting graphs generalizes Berge's idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more gener...
详细信息
The notion of augmenting graphs generalizes Berge's idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) problem. Recently, the augmenting graph approach has been successfully applied to solve MIS in various other special cases. However, our knowledge of augmenting graphs is still very limited and we do not even know what the minimal infinite classes of augmenting graphs are. In the present paper, we find an answer to this question and apply it to extend the area of polynomial-time solvability of the maximum independent set problem.
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. (C) 2015 Elsevier B.V. All rights reserved.
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. (C) 2015 Elsevier B.V. All rights reserved.
The VERTEX COLOURING problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced sub...
详细信息
The VERTEX COLOURING problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the VERTEX COLOURING problem in subclasses of triangle-free graphs obtained by forbidding graphs without cycles, i.e., forests, and prove polynomial-time solvability of the problem in many classes of this type. In particular, our paper, combined with some previously known results, provides a complete description of the complexity status of the problem in subclasses of triangle-free graphs obtained by forbidding a forest with at most 6 vertices. (C) 2011 Elsevier B.V. All rights reserved.
A few years ago a researcher attempted to show that one could minimize the total schedule length of lots of unit-time jobs by level scheduling. Unfortunately, this method can fail on problems where jobs have successor...
详细信息
A few years ago a researcher attempted to show that one could minimize the total schedule length of lots of unit-time jobs by level scheduling. Unfortunately, this method can fail on problems where jobs have successors at more than one level. In this paper, the method is altered to handle this problem.
Clique-width is a relatively new parameterization of graphs, philosophically similar to treewidth. Clique-width is more encompassing in the sense that a graph of bounded treewidth is also of bounded clique-width (but ...
详细信息
Clique-width is a relatively new parameterization of graphs, philosophically similar to treewidth. Clique-width is more encompassing in the sense that a graph of bounded treewidth is also of bounded clique-width (but not the converse). For graphs of bounded clique-width, given the clique-width decomposition, every optimization, enumeration or evaluation problem that can be defined by a monadic second-order logic formula using quantifiers on vertices, but not on edges, can be solved in polynomialtime. This is reminiscent of the situation for graphs of bounded treewidth, where the same statement holds even if quantifiers are also allowed on edges. Thus, graphs of bounded clique-width are a larger class than graphs of bounded treewidth, on which we can resolve fewer, but still many, optimization problems efficiently. One of the major open questions regarding clique-width is whether graphs of clique-width at most k, for fixed k, can be recognized in polynomialtime. In this paper, we present the first polynomial-time algorithm (O(n(2)m)) to recognize graphs of clique-width at most 3. (C) 2012 Elsevier B.V. with parts of the article (C) Bruce Reed. All rights reserved.
暂无评论