We introduce and explore a family of vertex-coloring problems, which, surprisingly enough, have not been considered before despite stemming from the problem of Wi-Fi channel assignment. Given a spectrum of colors, endowed with a matrix of interferences between each pair of colors, the Threshold Spectrum Coloring problem fixes the number of colors available and aims to minimize the interference threshold, i.e., the maximum of the interferences at the vertices. Conversely, the Chromatic Spectrum Coloring problem fixes a threshold and aims to minimize the number of colors for which respecting that threshold is possible. As the main theoretical results, we prove tight upper bounds for the solutions to each problem. Since both problems turn out to be NP-hard, we complete the scene with experimental results. We propose a DSATUR-based heuristic and study its performance to minimize the maximum vertex interference in Wi-Fi channel assignment, both for randomly-generated graphs and for a real-world scenario. Further, for all these graphs, we experimentally check the goodness of the theoretical bounds.
@cite_11 consider a weight function @math on the edges of the graph @math instead of a matrix @math of interferences between colors, defining the interference at a vertex to be the sum of weights of incident monochromatic edges. Although they bounds are similar to ours, using the same techniques, we further show tightness and follow a different, more detailed, scheme. Many other works impose conditions to the colors of the endpoints of any edge. Most of them can be framed into @cite_7 , where vertices at distance @math must get colors at distance @math . Particular instances include @cite_8 , where no two vertices at distance @math can have the same color, @cite_17 , where adjacent vertices must get colors @math apart and vertices at distance @math must get different colors, as well as @cite_13 , where adjacent vertices must get colors @math apart and vertices at distance @math must get colors @math apart.
@cite_11 @cite_7 @cite_8 @cite_13 @cite_17
2179569280 2116612642 2474966596 2045611333
Let @math be a graph with a threshold function @math such that @math for every vertex @math of @math , where @math is the degree of @math in @math . Suppose we are given a target set @math . This paper considers the following repetitive process on @math . At time step @math the vertices of @math are colored black and the other vertices are colored white. After that, at each time step @math , the colors of white vertices (if any) are updated according to the following rule. All white vertices @math that have at least @math black neighbors at the time step @math are colored black, and the colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The following optimization problem is called Target Set Selection: Find a target set @math of smallest possible size such that all vertices in @math are black at the end of the process. Such an @math is called an optimal target set for @math under the th... We prove two results regarding cycles in properly edge-colored graphs. First, we make a small improvement to the recent breakthrough work of Alon, Pokrovskiy and Sudakov who showed that every properly edge-colored complete graph @math on @math vertices has a rainbow cycle on at least @math vertices, by showing that @math has a rainbow cycle on at least @math vertices. Second, by modifying the argument of Hatami and Shor which gives a lower bound for the length of a partial transversal in a Latin Square, we prove that every properly colored complete graph has a Hamilton cycle in which at least @math different colors appear. For large @math , this is an improvement of the previous best known lower bound of @math of Andersen. Determining whether the vertices of a graph can be colored using @math different colors so that no two adjacent vertices receive the same color is a well-known NP-complete problem. Graph coloring is also of practical interest (for example, in estimating sparse Jacobians and in scheduling), and many heuristic algorithms have been developed. We present a heuristic algorithm based on the eigenvalue decomposition of the adjacency matrix of a graph. Eigenvectors point out bipartite-looking'''' subgraphs that are used to refine the coloring to a valid coloring. The algorithm optimally colors complete @math -partite graphs and certain other classes of graphs with regular structure. Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of [SIAM J. Comput., 28 (1999), pp. 1167--1181], we describe an @math -time algorithm APASP2 for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP2 is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k>2, we describe an @math -time algorithm APASPk for computing all distances in G with an additive one-sided error of at most k. We also give an @math -time algorithm @math for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in @math time. We say that a weighted graph F=(V,E') k-emulates an unweighted graph G=(V,E) if for every @math we have @math . We show that every unweighted graph on n vertices has a 2-emulator with @math edges and a 4-emulator with @math edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with @math edges and that such a 3-spanner can be built in @math time. We also describe an @math -time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3. Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p @math c n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p @math polylog(n) n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c. Consider the following probabilistic one-player game: The board is a graph with @math vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at random from all nonedges and is presented to the player, henceforth called Painter. Painter must assign one of @math available colors to each edge immediately, where @math is a fixed integer. The game is over as soon as a monochromatic copy of some fixed graph @math has been created, and Painter's goal is to “survive” for as many steps as possible before this happens. We present a new technique for deriving upper bounds on the threshold of this game, i.e., on the typical number of steps Painter will survive with an optimal strategy. More specifically, we consider a deterministic two-player variant of the game where the edges are chosen not randomly, but by a second player Builder. However, Builder has to adhere to the restriction that, for some real number @math , the ratio of edges to vertices in all subgraphs of the evolving board ne... For an unweighted graph @math , @math is a subgraph if @math , and @math is a Steiner graph if @math , and for any pair of vertices @math , the distance between them in @math (denoted @math ) is at least the distance between them in @math (denoted @math ). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) @math of a graph @math is a subgraph (resp., Steiner) @math -preserver of @math if for every pair of vertices @math with @math , @math . We show that any graph (resp., digraph) has a subgraph @math -preserver with at most @math edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner @math -preserver contains @math edges. However, we show that if one allows a directed Steiner (diSteiner) @math -preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner @math -preserver with @math arcs, and that this result is tight up to a constant factor. We also study @math -preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least @math one from another. We show that there exists a @math -preserving labeling scheme with labels of size @math , and that labels of size @math are required for any @math -preserving labeling scheme. When graph Ramsey theory is viewed as a game, "Painter" 2-colors the edges of a graph presented by "Builder". Builder wins if every coloring has a monochromatic copy of a fixed graph @math . In the on-line version, iteratively, Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class @math . Builder wins the game @math if a monochromatic copy of @math can be forced. The on-line degree Ramsey number @math is the least @math such that Builder wins @math when @math is the class of graphs with maximum degree at most @math . Our results include: 1) @math if and only if @math is a linear forest or each component lies inside @math . 2) @math , where @math . 3) @math for a tree @math , where @math and @math are two largest vertex degrees. 4) @math , with @math except for finitely many odd values of @math . 5) @math when @math . The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays "consistently". We introduce the following notion of compressing an undirected graph @math with (nonnegative) edge-lengths and terminal vertices @math . A distance-preserving minor is a minor @math (of @math ) with possibly different edge-lengths, such that @math and the shortest-path distance between every pair of terminals is exactly the same in @math and in @math . We ask: what is the smallest @math such that every graph @math with @math terminals admits a distance-preserving minor @math with at most @math vertices? Simple analysis shows that @math . Our main result proves that @math , significantly improving on the trivial @math . Our lower bound holds even for planar graphs @math , in contrast to graphs @math of constant treewidth, for which we prove that @math vertices suffice. We describe a new approximation algorithm for Max Cut. Our algorithm runs in @math time, where @math is the number of vertices, and achieves an approximation ratio of @math . In instances in which an optimal solution cuts a @math fraction of edges, our algorithm finds a solution that cuts a @math fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a @math fraction of edges, our spectral partitioning algorithm finds a set @math of vertices and a bipartition @math of @math such that at least a @math fraction of the edges incident on @math have one endpoint in @math and one endpoint in @math . (This can be seen as an analogue of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, var... For a positive parameter @math , the @math -bounded distance between a pair of vertices @math in a weighted undirected graph @math is the length of the shortest @math path in @math with at most @math edges, aka hops . For @math as above and @math , a @math -hopset of @math is a graph @math on the same vertex set, such that all distances in @math are @math -approximated by @math -bounded distances in @math . Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with @math edges, or with a hopbound @math . In this paper we devise a construction of linear-size hopsets with hopbound @math . This improves the previous bound almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm EN16 for computing hopsets with a constant (i.e., independent of @math ) hopbound requires @math time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from EN16 . We use our hopsets to devise a distributed routing scheme that exhibits near-optimal tradeoff between individual memory requirement @math of vertices throughout preprocessing and routing phases of the algorithm, and stretch @math , along with a near-optimal construction time @math , where @math is the hop-diameter of the input graph. This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data.Three results are proved within this model: • A 3-coloring of an n-cycle requires time @math . This bound is tight, by previous work of Cole and Vishkin. • Any algorithm for coloring the d-regular tree of radius r which runs for time at most @math requires at least @math colors. • In an n-vertex graph of largest degree @math , an @math -coloring may be found in time @math . The paper deals with a polling game on a graph. Initially, each vertex is colored white or black. At each round, each vertex is colored by the color shared by the majority of vertices in its neighborhood, at the previous round. (All recolorings are done simultaneously.) We say that a set W0 of vertices is a dynamic monopoly or dynamo if starting the game with the vertices of W0 colored white, the entire system is white after a finite number of rounds. D. Peleg (1998, Discrete Appl. Math.86, 262?273) asked how small a dynamic monopoly may be as a function of the number of vertices. We show that the answer is O(1). We study a one-parameter family of discrete dynamical systems called the @math -color firefly cellular automata (FCAs), which were introduced recently by the author. At each discrete time @math , each vertex in a graph has a state in @math , and a special state @math is designated as the blinking' state. At step @math , simultaneously for all vertices, the state of a vertex increments from @math to @math unless @math and at least one of its neighbors is in the state @math . A central question about this system is that on what class of network topologies synchrony is guaranteed to emerge. In a previous work, we have shown that for @math , every @math -coloring on a finite tree synchronizes iff the maximum degree is less than @math , and asked whether this behavior holds for all @math . In this paper, we answer the question positively for @math and negatively for all @math by constructing counterexamples on trees with maximum degree at most @math . We give the first improvement to the space approximation trade-off of distance oracles since the seminal result of Thorup and Zwick [STOC'01]. For unweighted graphs, our distance oracle has size @math and, when queried about vertices at distance @math , returns a path of length @math . For weighted graphs with @math edges, our distance oracle has size @math and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space @math . For unweighted graphs, this implies a @math space lower bound to achieve approximation @math . We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all @math . This immediately implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of @math -colorings of a @math -regular graph, for any @math , is maximized by a union of @math 's. This proves the @math case of a conjecture of Galvin and Tet ali. We give the first improvement to the space approximation trade-off of distance oracles since the seminal result of Thorup and Zwick. For unweighted undirected graphs, our distance oracle has size @math and, when queried about vertices at distance @math , returns a path of length at most 2d+1. For weighted undirected graphs with @math edges, our distance oracle has size @math and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space @math . For unweighted graphs, this implies a @math space lower bound to achieve approximation 2d+1. Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp. Given a set of @math n points, each is painted by one of the @math k given colors, we want to choose @math k points with distinct colors to form a color spanning set. For each color spanning set, we can construct the convex hull and the smallest axis-aligned enclosing rectangle, etc. Assuming that each point is chosen independently and identically from the subset of points of the same color, we propose an @math O ( n 2 ) time algorithm to compute the expected area of convex hulls of the color spanning sets and an @math O ( n 2 ) time algorithm to compute the expected perimeter of convex hulls of the color spanning sets. For the expected perimeter (resp. area) of the smallest perimeter (resp. area) axis-aligned enclosing rectangles of the color spanning sets, we present an @math O ( n log n ) (resp. @math O ( n 2 ) ) time algorithm. We also propose a simple approximation algorithm to compute the expected diameter of the color spanning sets. For the expected distance of the closest pair, we show that it is @math # P-complete to compute and there exists no polynomial time @math 2 n 1 - ? approximation algorithm to compute the probability that the closest pair distance of all color spanning sets equals to a given value @math d unless @math P = N P , even in one dimension and when each color paints two points. Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study @math -edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices @math and @math are @math -edge-connected if there are two edge-disjoint paths from @math to @math and two edge-disjoint paths from @math to @math . This relation partitions the vertices into blocks such that all vertices in the same block are @math -edge-connected. Differently from the undirected case, those blocks do not correspond to the @math -edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are @math -edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has @math edges and maintains the same @math -edge-connected blocks as the input graph.