Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.     

Finding Maximum Edge Bicliques in Convex Bipartite Graphs

A bipartite graph G=(A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v??A, vertices adjacent to v are consecutive in?B. A complete bipartite subgraph of a graph G is called a biclique of G. Motivated by an application to analyzing DNA microarray data, we study the problem of finding maximum edge bicliques in convex bipartite graphs. Given a bipartite graph G=(A,B,E) which is convex on B, we present a new algorithm that computes a maximum edge biclique of G in O(nlog?³ nlog?log?n) time and O(n) space, where n=|A|. This improves the current O(n ²) time bound available for the problem. We also show that for two special subclasses of convex bipartite graphs, namely for biconvex graphs and bipartite permutation graphs, a maximum edge biclique can be computed in O(n??(n)) and O(n) time, respectively, where n=min?(|A|,|B|) and ??(n) is the slowly growing inverse of the Ackermann function.     

Distributed MST for constant diameter graphs

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at most B bits for some parameter B. It is shown that the number of communication rounds necessary to compute an MST for graphs of diameter 4 or 3 can be as high as and , respectively. The asymptotic lower bounds hold for randomized algorithms as well. On the other hand, we observe that O(log n) communication rounds always suffice to compute an MST deterministically for graphs with diameter 2, when B = O(log n). These results complement a previously known lower bound of for graphs of diameter Ω(log n). An extended abstract of this work appears in Proceedings of 20th ACM Symposium on Principles of Distributed Computing, August 2001.     

Coloring inductive graphs on-line

In this paper we consider the problem of on-line graph coloring. In an instance of on-line graph coloring, the nodes are presented one at a time. As each node is presented, its edges to previously presented nodes are also given. Each node must be assigned a color, different from the colors of its neighbors, before the next node is given. LetA(G) be the number of colors used by algorithmA on a graphG and letx(G) be the chromatic number ofG. The performance ratio of an on-line graph coloring algorithm for a class of graphsC is max_{G C(A(G)/(G))}. We consider the class ofd-inductive graphs. A graphG isd-inductive if the nodes ofG can be numbered so that each node has at mostd edges to higher-numbered nodes. In particular, planar graphs are 5-inductive, and chordal graphs arex(G)-inductive. First Fit is the algorithm that assigns each node the lowest-numbered color possible. We show that ifG isd-inductive, then First Fit usesO(d logn) colors onG. This yields an upper bound ofo(logn) on the performance ratio of First Fit on chordal and planar graphs. First Fit does as well as any on-line algorithm ford-inductive graphs: we show that, for anyd and any on-line graph coloring algorithmA, there is ad-inductive graph that forcesA to use (d logn) colors to colorG. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookaheadl, if it must color nodei after examining only the firstl+i nodes. We show that, forl/logn, the lower bound ofd logn colors still holds.This research was supported by an IBM Graduate Fellowship.     

Clique Numbers of Random Subgraphs of Some Distance Graphs

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows:

$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$

where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

     

Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs

δ-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points u,v,w,x, the two larger of the distance sums d(u,v)+d(w,x),d(u,w)+d(v,x),d(u,x)+d(v,w) differ by at most?2δ. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted δ-hyperbolic graphs. Using the Layering Partition technique, we show that every n-vertex δ-hyperbolic graph with δ≥1/2 has an additive O(δlog?n)-spanner with at most O(δn) edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of δ-hyperbolic graphs with an additive error O(δlog?n). The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of n-vertex δ-hyperbolic graphs with δ≥1/2 admits a routing labeling scheme with O(δlog?² n) bit labels, O(δlog?n) additive stretch and O(log?₂(4δ)) time routing protocol, and a distance labeling scheme with O(log?² n) bit labels, O(δlog?n) additive error and constant time distance decoder.     

Existence and efficient construction of fast Fourier transforms on supersolvable groups

The linear complexityL _K(A) of a matrixA over a fieldK is defined as the minimal number of additions, subtractions and scalar multiplications sufficient to evaluateA at a generic input vector. IfG is a finite group andK a field containing a primitive exp(G)-th root of unity,L _K(G):= min{L _K(A)|A a Fourier transform forKG} is called theK-linear complexity ofG. We show that every supersolvable groupG has amonomial Fourier Transform adapted to a chief series ofG. The proof is constructive and gives rise to an efficient algorithm with running timeO(|G|²log|G|). Moreover, we prove that these Fourier transforms are efficient to evaluate:L _K(G)8.5|G|log|G| for any supersolvable groupG andL _K(G)1.5|G|log|G| for any 2-groupG.     

On the Advice Complexity of the k-server Problem Under Sparse Metrics

We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs. These algorithms require advice of (almost) linear size. We show that for graphs of size N and treewidth α, there is an online algorithm that receives O (n(log α + log log N))^* bits of advice and optimally serves any sequence of length n. We also prove that if a graph admits a system of μ collective tree (q, r)-spanners, then there is a (q + r)-competitive algorithm which requires O (n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, when provided with O (n log log N) bits of advice. On the other side, we prove that advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of length n even for the 2-server problem on a path metric of size N ≥ 3. Through another lower bound argument, we show that at least \(\frac {n}{2}(\log \alpha - 1.22)\) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 ≤ α < 2k.     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

Faster communication in known topology radio networks

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication primitives in arbitrary graphs. In particular, for the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D + O(log³ n), and a randomized algorithm for computing a radio schedule of length D + O(log² n). These results improve on the best currently known D + O(log⁴ n) time schedule due to Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Later we propose a new (efficiently computable) deterministic schedule that uses 2D + Δlog n + O(log³ n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time , for any network with the diameter D = Ω(log ⁱ⁺⁴ n), where i is an arbitrary integer constant i ≥ 0, see Gąsieniec et al. (Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity, vol. 3104, pp. 173–184, 2004). The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on the currently best known D + O(log³ n) time schedule proposed by Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Our new algorithm should be also seen as a separation result between planar and general graphs with small diameter due to the polylogarithmic inapproximability result for general graphs by Elkin and Kortsarz (Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, pp. 105–116, 2004; J. Algorithms 52(1), 8–25, 2004). The second author is supported in part by a grant from the Israel Science Foundation and by the Royal Academy of Engineering. Part of this research was performed while this author (Q. Xin) was a PhD student at The University of Liverpool.     

Local MST Computation with Short Advice

We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem ? is a way, for every possible input I of ?, to provide an “advice” (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem ? can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (?log?n?,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies $t\geq\tilde{\Omega}(\sqrt{n})We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem ℘ is a way, for every possible input I of ℘, to provide an “advice” (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem ℘ can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (⌈log n⌉,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies t 3 [(W)\tilde](?n)t\geq\tilde{\Omega}(\sqrt{n}). Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log n to constant.     

Distributed deterministic edge coloring using bounded neighborhood independence

We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2Δ ?1)-edge-coloring requires O(Δ) +  log* n time (Panconesi and Rizzi in Distrib Comput 14(2):97–100, 2001), where Δ is the maximum degree of the input graph. Also, recent results of Barenboim and Elkin (2010) for vertex-coloring imply that one can get an O(Δ)-edge-coloring in ${O(\Delta^{\epsilon}\cdot \log n)}$ time, and an ${O(\Delta^{1 + \epsilon})}$ -edge-coloring in O(log Δ log n) time, for an arbitrarily small constant ${\epsilon > 0}$ . In this paper we devise a significantly faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(Δ)-edge-coloring in ${O(\Delta^{\epsilon}) + \log* n}$ time, and an ${O(\Delta^{1 + \epsilon})}$ -edge-coloring in O(log Δ) +  log* n time. This result improves the state-of-the-art running time for deterministic edge-coloring with this number of colors in almost the entire range of maximum degree Δ. Moreover, it improves it exponentially in a wide range of Δ, specifically, for 2 ^Ω(log*n) ≤ Δ ≤ polylog(n). In addition, for small values of Δ (up to log^{1 - δ} n, for some fixed δ > 0) our deterministic algorithm outperforms all the existing randomized algorithms for this problem. Also, our algorithm is the first O(Δ)-edge-coloring algorithm that has running time o(Δ) + log* n, for the entire range of Δ. All previous (deterministic and randomized) O(Δ)-edge-coloring algorithms require ${\Omega(\min \{\Delta, \sqrt{\log n}\ \})}$ time. On our way to these results we study the vertex-coloring problem on graphs with bounded neighborhood independence. This is a large family of graphs, which strictly includes line graphs of r-hypergraphs (i.e., hypergraphs in which each hyperedge contains r or less vertices) for r =  O(1), and graphs of bounded growth. We devise a very fast deterministic algorithm for vertex-coloring graphs with bounded neighborhood independence. This algorithm directly gives rise to our edge-coloring algorithms, which apply to general graphs. Our main technical contribution is a subroutine that computes an O(Δ/p)-defective p-vertex coloring of graphs with bounded neighborhood independence in O(p ²) + log* n time, for a parameter p, 1 ≤ p ≤ Δ. In all previous efficient distributed routines for m-defective p-coloring the product m· p is super-linear in Δ. In our routine this product is linear in Δ, and this enables us to speed up the algorithm drastically.     

Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ² for any simple graph with maximum degree Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time \(\mathcal{O}\) (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple \(\mathcal{O}\) (logn) algorithm for the distance transform with respect to theL ₁-metric, an \(\mathcal{O}\) (log² n) algorithm for the transform with respect to theL _∞-metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time \(\mathcal{O}\) (log³ n).     

Time slot scheduling of compatible jobs

A version of weighted coloring of a graph is introduced which is motivated by some types of scheduling problems: each node v of a graph G corresponds to some operation to be processed (with a processing time w(v)), edges represent nonsimultaneity requirements (incompatibilities). We have to assign each operation to one time slot in such a way that in each time slot, all operations assigned to this slot are compatible; the length of a time slot will be the maximum of the processing times of its operations. The number k of time slots to be used has to be determined as well. So, we have to find a k-coloring = of G such that w(S ₁) + ⋅s +w(S _k ) is minimized where w(S _i ) = max {w(v) :v∊V}. Properties of optimal solutions are discussed, and complexity and approximability results are presented. Heuristic methods are given for establishing some of these results. The associated decision problems are shown to be NP-complete for bipartite graphs, for line-graphs of bipartite graphs, and for split graphs.     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

Collective Tree Spanners in Graphs with Bounded Parameters

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system $\mathcal{T}(G)In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system T(G)\mathcal{T}(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T ? T(G)T\in\mathcal{T}(G) exists such that d _T (x,y)≤d _G (x,y)+r. We describe a general method for constructing a “small” system of collective additive tree r-spanners with small values of r for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of O(?n)O(\sqrt{n}) collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog ₂ n collective additive tree 0-spanners, any weighted graph with clique-width at most k admits a system of klog _3/2 n collective additive tree (2w)(2\mathsf{w}) -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log ₂ n collective additive tree (2?c/2?w)(2\lfloor c/2\rfloor\mathsf{w}) -spanners and a system of 4log ₂ n collective additive tree (2(?c/3?+1)w)(2(\lfloor c/3\rfloor +1)\mathsf {w}) -spanners (here, w\mathsf{w} is the maximum edge weight in G). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4log ₂ n collective additive tree (2w)(2\mathsf{w}) -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.     

An improved version of the Cocke-Younger-Kasami algorithm

The Cocke-Younger-Kasami algorithm (CYK) always requires 0(n³) time and 0(n²) space to recognize a trial sentence ω = w₁w₂…w_n, given an e-free context-free grammar in Chomsky Normal form. The same inductive rule that underlies the CYK algorithm may be used to produce a variant that computes the same information but requires (1) a maximum of 0(n³) time and 0(n²) space, and (2) only 0(s(n)) space and time for an unambiguous grammar, where s(n) is the number of triples (A,i,j) for which a nonterminal symbol A derives w_iw_i+1…w_i+j?1. In this case, time and space consumed are at worst 0(n²).It is shown in addition, for any grammar, that a parse may be obtained from the table left from the recognition algorithm in time 0(s(n)) whether or not the grammar is ambiguous. The same procedure for the CYK algorithm requires time 0(n²).The performance of our variant is quite similar to that of the Earley algorithm except that the Earley algorithm substitutes for s(n), a function which is usually smaller.The model we use of a RAM is strictly identical to the model used in the CYK algorithm. CR categories: 4.20, 5.23, 5.25.