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.
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by chi(a)'(G), is the least number of colors in an acyclic edge coloring of G. L...
详细信息
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by chi(a)'(G), is the least number of colors in an acyclic edge coloring of G. Let G be a planar graph with maximum degree Delta(G). In this paper, we show that chi(a)'(G) <= Delta(G) + 4, if G contains no 4-cycle;chi(a)'(G) <= Delta(G) + 5, if G contains no intersecting triangles;and chi(a)'(G) <= Delta(G) + 6 if G contains no adjacent triangles. (C) 2011 Elsevier B.V. All rights reserved.
Given an undirected graph with n vertices, the MAXIMUM LEAF SPANNING TREE problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in...
详细信息
Given an undirected graph with n vertices, the MAXIMUM LEAF SPANNING TREE problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4(k)poly(n)) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [16] improved the branching and obtained a running time of O(3.72(k)poly(n)). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the CONNECTED DOMINATING SET problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Omega(2(n)) barrier and proposed an O(1.9407(n))-time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of O(1.8966(n)) has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Omega(1.4422(n)) for the worst case running time of our algorithm. (C) 2011 Elsevier B.V. All rights reserved.
The Nemhauser-Trotter local optimization theorem applies to the NP-hard VERTEX COVER problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotter's resul...
详细信息
The Nemhauser-Trotter local optimization theorem applies to the NP-hard VERTEX COVER problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotter's result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away "easy parts" of the input instance, finally leaving a "hard core" whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of VERTEX COVER, called BOUNDED-DEGREE VERTEX DELETION. For some fixed d >= 0, BOUNDED-DEGREE VERTEX DELETION asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. VERTEX COVER is the special case of d = 0. Our generalization of the Nemhauser-Trotter-Theorem implies that BOUNDED-DEGREE VERTEX DELETION, parameterized by k, admits an O (k)-vertex problem kernel for d <= 1 and, for any epsilon > 0, an O(k(1+epsilon))-vertex problem kernel for d >= 2. Finally, we provide a W[2]-completeness result for BOUNDED-DEGREE VERTEX DELETION in case of unbounded d-values. (C) 2010 Elsevier Inc. All rights reserved.
In this note we introduce the concept of equitable d-relaxed coloring. We prove that each graph with maximum degree at most r admits an equitable 1-relaxed r-coloring and provide a polynomial-time algorithm for constr...
详细信息
In this note we introduce the concept of equitable d-relaxed coloring. We prove that each graph with maximum degree at most r admits an equitable 1-relaxed r-coloring and provide a polynomial-time algorithm for constructing such a coloring. (C) 2011 Elsevier B.V. All rights reserved.
A t-spanner of a graph G is its spanning subgraph S such that the distance between every pair of vertices in S is at most t times their distance in G. The SPARSEST t-SPANNER problem asks to find, for a given graph G a...
详细信息
A t-spanner of a graph G is its spanning subgraph S such that the distance between every pair of vertices in S is at most t times their distance in G. The SPARSEST t-SPANNER problem asks to find, for a given graph G and an integer t, a t-spanner of G with the minimum number of edges. The problem is known to be NP-hard for all t >= 2, and, even more, it is NP-hard to approximate it with ratio O(log n) for every t >= 2. For t >= 5, the problem remains NP-hard for planar graphs and the approximability status of the problem on planar graphs was open. We resolve this open issue by showing that the SPARSEST t-SPANNER problem admits the efficient polynomial time approximation scheme (EPTAS) for every t >= 1. Our result holds for a much wider class of graphs, namely, the class of apex-minor-free graphs, which contains the classes of planar and bounded genus graphs. Moreover, it is possible to extend our results to weighted apex-minor free graphs, when the maximum edge weight is bounded by some constant. (C) 2010 Elsevier B.V. All rights reserved.
We consider a network with unreliable communication channels and perfectly reliable nodes. The diameter constrained reliability for such a network is defined as the probability that between each pair of nodes, there e...
详细信息
We consider a network with unreliable communication channels and perfectly reliable nodes. The diameter constrained reliability for such a network is defined as the probability that between each pair of nodes, there exists a path consisting of operational edges whose number is upper bounded by a given integer. The problem of computing this characteristic is NP-hard, just like the problem of computing the probability of a network's connectivity. We propose a formula that lets one use junction points to compute the reliability of a two-pole system with diameter constraints, which makes the computations faster.
Motivated by reliability considerations in data deduplication for storage systems, we introduce the problem of flexible coloring. Given a hypergraph H and the number of allowable colors k, a flexible coloring of H is ...
详细信息
Motivated by reliability considerations in data deduplication for storage systems, we introduce the problem of flexible coloring. Given a hypergraph H and the number of allowable colors k, a flexible coloring of H is an assignment of one or more colors to each vertex such that, for each hyperedge, it is possible to choose a color from each vertex's color list so that this hyperedge is strongly colored (i.e., each vertex has a different color). Different colors for the same vertex can be chosen for different incident hyperedges (hence the term flexible). The goal is to minimize color consumption, namely, the total number of colors assigned, counting multiplicities. Flexible coloring is NP-hard and trivially s - (s-1)k/n approximable, where s is the size of the largest hyperedge, and n is the number of vertices. Using a recent result by Bansal and Khot, we show that if k is constant, then it is UGC-hard to approximate to within a factor of s - epsilon, for arbitrarily small constant epsilon > 0. Lastly, we present an algorithm with an s - (s-1)k/k' approximation ratio, where k' is number of colors used by a strong coloring algorithm for H. (C) 2011 Elsevier B.V. All rights reserved.
L(2, 1)-labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at...
详细信息
L(2, 1)-labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. It is known that for any k >= 4 it is NP-complete to determine if a graph has a L(2, 1)-labeling with no label greater than k. In this paper we present a new bound on complexity of an algorithm for finding an optimal L(2, 1)-labeling (i.e. an L(2, 1)-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from O*(3.5616(n)) to O*(3.2361(n)). Moreover, we establish a lower complexity bound of the presented algorithm, which is Omega*(3.0739(n)). (C) 2011 Elsevier B.V. All rights reserved.
A tournament T = (V, A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the FEEDBACK ARC SET problem asks whethe...
详细信息
A tournament T = (V, A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the FEEDBACK ARC SET problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The FEEDBACK ARC SET problem restricted to tournaments is known as the k-FEEDBACK ARC SET IN TOURNAMENTS (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T' on O(k) vertices. In fact, given any fixed epsilon > 0, the kernelized instance has at most (2 + epsilon)k vertices. Our result improves the previous known bound of O(k(2)) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST. (C) 2010 Elsevier Inc. All rights reserved.
暂无评论