Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfi...
详细信息
Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. (C) 2010 Elsevier B.V. All rights reserved.
A confluent and terminating reduction system is introduced for graphs, which preserves the number of their perfect matchings. A union-find algorithm is presented to carry out reduction in almost linear time. The Konig...
详细信息
A confluent and terminating reduction system is introduced for graphs, which preserves the number of their perfect matchings. A union-find algorithm is presented to carry out reduction in almost linear time. The Konig property is investigated in the context of reduction by introducing the Konig deficiency of a graph G as the difference between the vertex covering number and the matching number of G. It is shown that the problem of finding the Konig deficiency of a graph is NP-complete even if we know that the graph reduces to the empty graph. Finally, the Konig deficiency of graphs G having a vertex v such that G-v has a unique perfect matching is studied in connection with reduction.
Recently Lexicographic Breadth First Search (LBFS) has received considerable attention and has often been employed in a multi-sweep fashion. One variant of LBFS called LBFS+ breaks ties by choosing the last vertex of ...
详细信息
Recently Lexicographic Breadth First Search (LBFS) has received considerable attention and has often been employed in a multi-sweep fashion. One variant of LBFS called LBFS+ breaks ties by choosing the last vertex of the tied set in a previous LBFS. This has motivated the study of vertices that may appear last in an LBFS (called end-vertices). In this paper, we present various theoretical and algorithmic results concerning end-vertices. (C) 2009 Elsevier B.V. All rights reserved.
Let c be a proper edge coloring of a graph G. If there exists no bicolored cycle in G with respect to c, then c is called an acyclic edge coloring of G. Let G be a planar graph with maximum degree Delta and girth g. I...
详细信息
Let c be a proper edge coloring of a graph G. If there exists no bicolored cycle in G with respect to c, then c is called an acyclic edge coloring of G. Let G be a planar graph with maximum degree Delta and girth g. In Dong and Xu (2010) [8], Dong and Xu proved that G admits an acyclic edge coloring with Delta(G) colors if Delta >= 8 and g >= 7, or Delta >= 6 and g >= 8, or Delta >= 5 and g >= 9, or Delta >= 4 and g >= 10, or Delta >= 3 and g >= 14. In this note, we fix a small gap in the proof of Dong and Xu (2010) [8], and generalize the above results to toroidal graphs. (C) 2011 Elsevier B.V. All rights reserved.
We present a new implementation of the Kou, Markowsky and Berman algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V . The total distance ...
详细信息
We present a new implementation of the Kou, Markowsky and Berman algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V . The total distance of all edges of this Steiner tree is at most 2(1-1/ l ) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(| E |+| V |log| V |) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph.
The property M(k) is a concept associated with the unique list coloring. A graph G has the property M(k) if for any collection of lists assigned to its vertices, each of size k, either there is no list coloring for G ...
详细信息
The property M(k) is a concept associated with the unique list coloring. A graph G has the property M(k) if for any collection of lists assigned to its vertices, each of size k, either there is no list coloring for G or there are at least two k-list colorings. The existing research results indicate that K-1,K-1,K-1,K-r and K-1*r,K-3 have the property M(3), and in addition K-1*5,K-r and K-1*r,K-5 have the property M(4) for every r >= 2. The results above are extended to every k in this paper. We will show that for every r >= 1, k >= 2, K-1*r,K- (2k-3) and K-1*(2k-3),K-r have the property M(k). The conclusion will pave the way to characterizing unique k-list colorable complete multipartite graphs. (C) 2014 Elsevier B.V. All rights reserved.
We present a new polynomial-time heuristic algorithm for finding a solution to the Travelling Salesman Problem (TSP) for any complete and edge-weighted graph K n , with a set of vertices V and a set of edges E where |...
详细信息
We present a new polynomial-time heuristic algorithm for finding a solution to the Travelling Salesman Problem (TSP) for any complete and edge-weighted graph K n , with a set of vertices V and a set of edges E where | V | = n . In a few words, this method is based on the idea of linking the elements of V progressively, one by one, in such a way that the vertex selection which produces fewest disturbances to the other vertices not yet connected, will be selected as the next vertex to join to the subset of already connected vertices. When the cost of the result is compared to the cost of the best circuit, it appears that a good sub-solution is obtained in most of the cases tested. Moreover, comparison tests made between the heuristic introduced and the well-known Quick method, produce a better behaviour, for almost every case, in the first approach.
Social tagging systems have gained increasing popularity as a method of annotating and categorizing a wide range of different web resources. Web search that utilizes social tagging data suffers from an extreme example...
详细信息
Social tagging systems have gained increasing popularity as a method of annotating and categorizing a wide range of different web resources. Web search that utilizes social tagging data suffers from an extreme example of the vocabulary mismatch problem encountered in traditional information retrieval (IR). This is due to the personalized, unrestricted vocabulary that users choose to describe and tag each resource. Previous research has proposed the utilization of query expansion to deal with search in this rather complicated space. However, non-personalized approaches based on relevance feedback and personalized approaches based on co-occurrence statistics only showed limited improvements. This paper proposes a novel query expansion framework based on individual user profiles mined from the annotations and resources the user has marked. The underlying theory is to regularize the smoothness of word associations over a connected graph using a regularizer function on terms extracted from top-ranked documents. The intuition behind the model is the prior assumption of term consistency: the most appropriate expansion terms for a query are likely to be associated with, and influenced by terms extracted from the documents ranked highly for the initial query. The framework also simultaneously incorporates annotations and web documents through a Tag-Topic model in a latent graph. The experimental results suggest that the proposed personalized query expansion method can produce better results than both the classical non-personalized search approach and other personalized query expansion methods. Hence, the proposed approach significantly benefits personalized web search by leveraging users' social media data.
We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pa...
详细信息
We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 59% over unitigs and 26% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 90% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26x over unitigs and 2.10x over previous work.
暂无评论