The well-known Brooksʼ Theorem says that each graph G of maximum degree k ⩾ 3 is k -colorable unless G = K k + 1 . We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood.
The well-known Brooksʼ Theorem says that each graph G of maximum degree k ⩾ 3 is k -colorable unless G = K k + 1 . We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood.
Computing the winning set for Buchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solvi...
详细信息
ISBN:
(纸本)9781611972108
Computing the winning set for Buchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is O{top}~(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the O{top}~(n·m) boundary by presenting a new technique that reduces the running time to O(n~2). This bound also leads to O(n~2) time algorithms for computing the set of almost-sure winning vertices for Buchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of {top}O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n~3)), and (3) in Markov decision processes (improving for m ＞ n~(4/3) an earlier bound of O(min(m~(1.5),m· n~(2/3))). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n~2), which is an improvement over earlier bounds for m ＞ n~(4/3). Finally, we show how to maintain the winning set for Buchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.
In this paper a new mixed nodal-mesh formulation of the PEEC method is proposed. Based on the hypothesis that charges reside only on the surface of conductors and that current density is solenoidal inside them, a nove...
详细信息
ISBN:
(纸本)9781424416998
In this paper a new mixed nodal-mesh formulation of the PEEC method is proposed. Based on the hypothesis that charges reside only on the surface of conductors and that current density is solenoidal inside them, a novel scheme is developed fully exploiting the physical properties of charges and currents. It comes out that the presented approach allows to reduce the number of unknowns while preserving the accuracy. An elegant and efficient algorithm, based on graph theory, is proposed to automatically search independent loops on three dimensional rectangular grids such as those arising in volumetric PEEC formulation. The method is validated through numerical results that confirm the accuracy of the proposed formulation from DC-to-daylight and its capability to provide memory saving.
We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to ...
详细信息
We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs. We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in 1,...,M, it runs in (O) over tilde(root Mn(omega+3)/2) time where omega < 2.376 is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in <(O)over tilde>(Mn(omega)t) time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of epsilon in (O) over tilde (n((omega+6)/3)) time. (C) 2011 Elsevier B.V. All rights reserved.
This paper presents the ideas, experiments and specifications related to the Supervised TextRank (STR) technique, a word tagging method based on the TextRank algorithm. The main innovation of STR technique is the use ...
详细信息
This paper presents the ideas, experiments and specifications related to the Supervised TextRank (STR) technique, a word tagging method based on the TextRank algorithm. The main innovation of STR technique is the use of a graph-based ranking algorithm similar to PageRank in a supervised fashion, gathering the information needed to build the graph representations of the text from a tagged corpus. We also propose a flexible graph specification language that allows to easily experiment with multiple configurations for the topology of the graph and for the information associated to the nodes and the edges. We have carried experiments in the Part-Of-Speech task, a common tagging problem in Natural Language Processing. In our best result we have achieved a precision of 96.16%, at the same level of the best tagging tools.
We present a simple unified algorithmic process which uses either LexBFS or MCS on a chordal graph to generate the minimal separators and the maximal cliques in linear time in a single pass. (C) 2011 Elsevier B.V. All...
详细信息
We present a simple unified algorithmic process which uses either LexBFS or MCS on a chordal graph to generate the minimal separators and the maximal cliques in linear time in a single pass. (C) 2011 Elsevier B.V. All rights reserved.
A set M subset of E is called an acyclic matching of a graph G = (V, E) if no two edges in M are adjacent and the subgraph induced by the set of end vertices of the edges of M is acyclic. Given a positive integer k an...
详细信息
A set M subset of E is called an acyclic matching of a graph G = (V, E) if no two edges in M are adjacent and the subgraph induced by the set of end vertices of the edges of M is acyclic. Given a positive integer k and a graph G = (V, E), the acyclic matching problem is to decide whether G has an acyclic matching of cardinality at least k. Goddard et al. (Discrete Math. 293(1-3) (2005) 129-138) introduced the concept of the acyclic matching problem and proved that the acyclic matching problem is NP-complete for general graphs. In this paper, we propose an O(n + m) time algorithm to find a maximum cardinality acyclic matching in a chain graph having n vertices and m edges and obtain an expression for the number of maximum cardinality acyclic matchings in a chain graph. We also propose a dynamic programming-based O(n+ m) time algorithm to find a maximum cardinality acyclic matching in a bipartite permutation graph having n vertices and m edges. Finally, we strengthen the complexity result of the acyclic matching problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs.
We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been inve...
详细信息
We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting.
The Map Reduce framework is currently the de facto standard used throughout both industry and academia for petabyte scale data analysis. As the input to a typical MapReduce computation is large, one of the key require...
详细信息
ISBN:
(纸本)9781450307437
The Map Reduce framework is currently the de facto standard used throughout both industry and academia for petabyte scale data analysis. As the input to a typical MapReduce computation is large, one of the key requirements of the framework is that the input cannot be stored on a single machine and must be processed in parallel. In this paper we describe a general algorithmic design technique in the MapReduce framework called filtering. The main idea behind filtering is to reduce the size of the input in a distributed fashion so that the resulting, much smaller, problem instance can be solved on a single machine. Using this approach we give new algorithms in the MapReduce framework for a variety of fundamental graph problems for sufficiently dense graphs. Specifically, we present algorithms for minimum spanning trees, maximal matchings, approximate weighted matchings, approximate vertex and edge covers and minimum cuts. In all of these cases, we parameterize our algorithms by the amount of memory available on the machines allowing us to show tradeoffs between the memory available and the number of MapReduce rounds. For each setting we will show that even if the machines are only given substantially sublinear memory, our algorithms run in a constant number of MapReduce rounds. To demonstrate the practical viability of our algorithms we implement the maximal matching algorithm that lies at the core of our analysis and show that it achieves a significant speedup over the sequential version.
At the core of the Robertson-Seymour theory of graph minors lies a powerful decomposition theorem which captures, for any fixed graph H, the common structural features of all the graphs which do not contain H as a min...
详细信息
ISBN:
(纸本)9781450306911
At the core of the Robertson-Seymour theory of graph minors lies a powerful decomposition theorem which captures, for any fixed graph H, the common structural features of all the graphs which do not contain H as a minor. Robertson and Seymour used this result to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation, as well as give a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed. The theorem has since found numerous applications, both in graph theory and theoretical computer science. The original proof runs more than 400 pages and the techniques used are highly non-trivial. In this paper, we give a simplified algorithm for finding the decomposition based on a new constructive proof of the decomposition theorem for graphs excluding a fixed minor H. The new proof is both dramatically simpler and shorter, making these results and techniques more accessible. The algorithm runs in time O(n(3)), as does the original algorithm of Robertson and Seymour. Moreover, our proof gives an explicit bound on the constants in the O notation, whereas the original proof of Robertson and Seymour does not.
暂无评论