Let G be any finite graph. A mapping c : E(G) -> {1, ... , k} is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, f...
详细信息
Let G be any finite graph. A mapping c : E(G) -> {1, ... , k} is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges that have colour i or j is acyclic. The smallest number k of colours such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by chi'(a)(G). Determining the acyclic chromatic index of a graph is a hard problem, both from theoretical and algorithmical point of view. In 1991, Alon et al. proved that chi'(a)(G) <= 64 Delta(G) for any graph G of maximum degree Delta(G). This bound was later improved to 16 Delta(G) by Molloy and Reed. In general, the problem of computing the acyclic chromatic index of a graph is NP-complete. Only a few algorithms for finding acyclic edge colourings have been known by now. Moreover, these algorithms work only for graphs from particular classes. In our paper, we prove that chi'(a) (G) <= (t - 1)Delta(G) + p for every graph G which satisfies the condition that vertical bar E(G')vertical bar <= t vertical bar V(G')vertical bar - 1 for each subgraph G' subset of G, where t >= 2 is a given integer, the constant p = 2t(3) - 3t + 2. Based on that result, we obtain a polynomial algorithm which computes such a colouring. The class of graphs covered by our theorem is quite rich, for example, it contains all t-degenerate graphs. (C) 2010 Elsevier B.V. All rights reserved.
作者：
PIRILLO, GIAMI
CNR viale Morgagni 67/A 50134 Firenze Italy
Let A be an alphabet and f be a right infinite word on A. If f is not ultimately periodic then there exists an infinite set {v,(i)\i greater-than-or-equal 0} of (finite) words on A such that f = v0v1...v(i)...,{v(i)\i...
详细信息
Let A be an alphabet and f be a right infinite word on A. If f is not ultimately periodic then there exists an infinite set {v,(i)\i greater-than-or-equal 0} of (finite) words on A such that f = v0v1...v(i)...,{v(i)\i greater-than-or-equal-to 1} is a biprefix code and v(i) not-equal v(j) for positive integers i not-equal j.
The authors review nonserial dynamic programming and the Planar Separator Theorem. They then show how to modify a counting algorithm of R. J. Lipton and R. E. Tarjan for finding a maximum independent-set so as to also...
详细信息
The authors review nonserial dynamic programming and the Planar Separator Theorem. They then show how to modify a counting algorithm of R. J. Lipton and R. E. Tarjan for finding a maximum independent-set so as to also compute the number of maximum independent-sets in a certain time. This algorithm is extended to several additional counting problems.
The delta-matching problem is a special version of approximate pattern-matching, motivated by applications in musical information retrieval, where the alphabet Sigma is an interval of integers. We investigate relation...
详细信息
The delta-matching problem is a special version of approximate pattern-matching, motivated by applications in musical information retrieval, where the alphabet Sigma is an interval of integers. We investigate relations between delta-matching and pattern-matching with don't care symbol * (a symbol matching every symbol, including itself). We show that the delta-matching is reducible to k instances of pattern-matching with don't cares. We investigate how the numbers delta and k are related by introducing delta-distinguishing families H of morphisms. The size of H corresponds to k. We show that for minimal families H we have \H\ = Theta (delta). (C) 2002 Elsevier Science B.V. All rights reserved.
In this paper we present a concise O(n) implementation of Cleary's algorithm for generating a sequence of restricted rotations between any two binary trees. The algorithm is described directly in terms of the bina...
详细信息
In this paper we present a concise O(n) implementation of Cleary's algorithm for generating a sequence of restricted rotations between any two binary trees. The algorithm is described directly in terms of the binary trees, without using any intermediate representation. (C) 2004 Elsevier B.V. All rights reserved.
A restricted edge cut of a graph X is an edge set whose removal disconnects X into nontrivial components. The cardinality of the minimum restricted edge cut is the restricted edge connectivity, denoted by lambda '...
详细信息
A restricted edge cut of a graph X is an edge set whose removal disconnects X into nontrivial components. The cardinality of the minimum restricted edge cut is the restricted edge connectivity, denoted by lambda '(X). If X has restricted edge cuts and lambda '(X) achieves the upper bound of the restricted edge connectivity, X is said to be lambda'-optimal. In this work, we will prove that for all but a few exceptions, the mixed Cayley graph is lambda'-optimal. (C) 2011 Elsevier Ltd. All rights reserved.
Detecting spatial regularity in images arises in computer vision, scene analysis, military applications, and other areas. In this paper we present an O(n(5/2)) algorithm that reports all maximal equally-spaced colline...
详细信息
Detecting spatial regularity in images arises in computer vision, scene analysis, military applications, and other areas. In this paper we present an O(n(5/2)) algorithm that reports all maximal equally-spaced collinear subsets. The algorithm is robust in that it can tolerate noise or imprecision that may be inherent in the measuring process, where the error threshold is a user-specified parameter. Our method also generalizes to higher dimensions. (C) 1999 Elsevier Science B.V. All rights reserved.
The tree and tour cover problems on an edge-weighted graph are to compute a minimum weight tree and closed walk, respectively, whose vertices form a vertex cover. Both problems are NP-hard. In this note we give strong...
详细信息
The tree and tour cover problems on an edge-weighted graph are to compute a minimum weight tree and closed walk, respectively, whose vertices form a vertex cover. Both problems are NP-hard. In this note we give strongly polynomial time, constant factor approximation algorithms for both problems. An interesting feature of our algorithms is how they combine approximations of other problems, namely the weighted vertex cover, traveling salesman, and Steiner tree problems.
Due to differences in propagation delays of transmission paths in a combinational network, a change in input combination might cause a momentary incorrect output, which is known as static hazard. This type of temporar...
详细信息
Due to differences in propagation delays of transmission paths in a combinational network, a change in input combination might cause a momentary incorrect output, which is known as static hazard. This type of temporary fault may be avoided by introducing some redundant minterms in the network. In the present work, a computer algorithm has been developed for hazard-free minimization of incompletely specified switching functions which eventually uses the consensus operation in the minimization procedure. Bit-level manipulation has been used to reduce time and space complexity of the developed algorithm.
In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G(n)} be a sequence of graphs G(0), G(1), G(2),... that belong to a particul...
详细信息
In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G(n)} be a sequence of graphs G(0), G(1), G(2),... that belong to a particular class. We consider graphs of the form K-n - G(n) that result from the complete graph K-n after removing a set of edges that span G(n). We study the spanning tree behaviour of the sequence {K-n - G(n)} when n --> infinity and the number of edges of G(n) scales according to n. More specifically, we define the spanning tree indicator alpha({G(n)}), a quantity that characterizes the spanning tree behaviour of {K-n - G(n)}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges). (C) 2004 Elsevier B.V. All rights reserved.
暂无评论