An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the leas...
详细信息
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G. In this paper, we show that any graph of maximum degree 5 has acyclic chromatic number at most 9, and we give a linear time algorithm that achieves this bound. (c) 2007 Elsevier B.V. All rights reserved.
In this paper we present a parameterized algorithm that solves the Convex Recoloring problem for trees in O(256(k) (*) poly(n)). This improves the currently best upper bound of O(k(k/log k)(k) (*) poly(n)) achieved by...
详细信息
In this paper we present a parameterized algorithm that solves the Convex Recoloring problem for trees in O(256(k) (*) poly(n)). This improves the currently best upper bound of O(k(k/log k)(k) (*) poly(n)) achieved by Moran and Snir. (c) 2007 Elsevier B.V. All rights reserved.
This book contains Volumes 4 and 5 of the Journal of graph algorithms and Applications (JGAA). The first book of this series, graph algorithms and Applications 1, published in March 2002, contains Volumes 1-3 of *** i...
详细信息
ISBN:
(数字)9789812794741
ISBN:
(纸本)9789812388551
This book contains Volumes 4 and 5 of the Journal of graph algorithms and Applications (JGAA). The first book of this series, graph algorithms and Applications 1, published in March 2002, contains Volumes 1-3 of *** is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design. The journal is supported by distinguished advisory and editorial boards, has high scientific standards, and takes advantage of current electronic document technology. The electronic version of JGAA is available on the Web at ***/.graph algorithms and Applications 2 presents contributions from prominent authors and includes selected papers from the Dagstuhl Seminar on graph algorithms and Applications and the Symposium on graph Drawing in 1998. All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to constru...
详细信息
Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to construct an elimination tree of minimum height. On the other hand, an optimal vertex ranking can readily be found directly from an elimination tree of minimum height. On n-vertex trees, the optimal vertex ranking problem already has a linear-time algorithm in the literature. However, there is no linear-time algorithm for the problem of finding a minimum height elimination tree. A naive algorithm for this problem requires O(n log n) time. In this paper, we propose a linear-time algorithm for constructing a minimum height elimination tree of a tree. (c) 2007 Elsevier Inc. All rights reserved.
Let l be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length exp(Omega(root log l/ log log l)) in polynomial time. This implies th...
详细信息
Let l be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length exp(Omega(root log l/ log log l)) in polynomial time. This implies the same bound for the longest cycle, longest vw-path, and longest path. The previous best bound for longest path is length Omega((log l)(2)/ log log l) due to Bjorklund and Husfeldt. Our approach, which builds on Bjorklund and Husfeldt's, uses cycles to enlarge cycles. This self-reducibility allows the approximation method to be iterated.
To exploit the similarity information hidden in the hyperlink structure of the Web, this paper introduces algorithms scalable to graphs with billions of vertices on a distributed architecture. The similarity of multis...
详细信息
To exploit the similarity information hidden in the hyperlink structure of the Web, this paper introduces algorithms scalable to graphs with billions of vertices on a distributed architecture. The similarity of multistep neighborhoods of vertices are numerically evaluated by similarity functions including SimRank [1], a recursive refinement of cocitation, and PSimRank, a novel variant with better theoretical characteristics. Our methods are presented in a general framework of Monte Carlo similarity search algorithms that precompute an index database of random fingerprints, and at query time, similarities are estimated from the fingerprints. We justify our approximation method by asymptotic worst-case lower bounds: We show that there is a significant gap between exact and approximate approaches, and suggest that the exact computation, in general, is infeasible for large-scale inputs. We were the first to evaluate SimRank on real Web data. On the Stanford WebBase [2] graph of 80M pages the quality of the methods increased significantly in each refinement step until step four.
Streett/Rabin games are an adequate model of strong fairness in reactive systems. We show here some results about their stochastic version. We extend the known lower bound in memory for the pure winning strategies of ...
详细信息
Streett/Rabin games are an adequate model of strong fairness in reactive systems. We show here some results about their stochastic version. We extend the known lower bound in memory for the pure winning strategies of the Streett player to randomized strategies. We also propose algorithms computing the almost sure winning regions of both players in stochastic Streett/Rabin games. The Rabin algorithm also yields directly a pure memoryless almost-sure winning strategy. (c) 2007 Elsevier B.V. All rights reserved.
Given an edge-weighted rooted tree T and a positive integer p ( 0 is a prescribed constant. (C) 2007 Elsevier B.V. All rights reserved.
Given an edge-weighted rooted tree T and a positive integer p (<= n), where n is the number of vertices in T, we cover all vertices in T by a set of p subtrees each of which contains the root r of T. The minmax rooted-tree cover problem asks to find such a set of p subtrees so as to minimize the maximum weight of the subtrees in the set. In this paper, we propose an 0(n) time (2 + epsilon) -approximation algorithm to the problem, where epsilon > 0 is a prescribed constant. (C) 2007 Elsevier B.V. All rights reserved.
We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which i...
详细信息
We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to O(n center dot polylog n) bits. Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(alpha(n)), for determining k-vertex and k-edge connectivity O(k(2)n) and O(n center dot logn) respectively for any constant k and for computing a minimum spanning forest O(log n). All these time bounds we reduce to O(1). Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems. (c) 2007 Elsevier B.V. All rights reserved.
We give improved parameterized algorithms for two '' edge '' problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite ...
详细信息
We give improved parameterized algorithms for two '' edge '' problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include: (i) a kernel with at most alpha k vertices and beta k edges for MAXCUT. Here 0 < alpha <=, 1 and 1 < beta <= 2. Values of alpha and beta depends on the number of vertices and the edges in the graph;(ii) a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;(iii) an O-*(1.2418(k)) parameterized algorithm for MAXCUT in undirected graphs. This improves the O-*(1.4143(k))(1) algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];(iv) an O-*(2(k)) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;(v) an O-*(2(k)) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O-*(4(k)) presented in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];(vi) an O-*(16(k)) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2 + k arcs. This improves the O-*(2(k)) algorithm given in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458]. In addition, we show that if a directed graph has minimum out degree at least f (n) (some function of n) th
暂无评论