 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 8
1. New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks
In this paper we study a semi on-line version of the classical multiprocessor scheduling problem on two identical processors. We assume that the sum of the tasks and an upper bound gamma on the size of each task are known. Each task has to be assigned upon arrival and the assignment cannot be changed later. The objective is the minimization of the maximum completion time on the processors. In this paper we propose new algorithms and improve known lower and upper bounds on the competitive ratio. Algorithms and bounds depend on the value of gamma. An optimal algorithm is obtained for gamma in the interval [ 1/n,2(n+1)/n(2n+1) ] and gamma = (2n-1)/2n(n-1), where n is any integer value larger or equal 2.
2. On Sampling Colorings of Bipartite Graphs
We study the problem of efficiently sampling k-colorings of bipartite graphs. We show that a class of markov chains cannot be used as efficient samplers. Precisely, we show that, for any k, 6 ≤ k ≤ n^\1/3-ε \, ε > 0 fixed, \emphalmost every bipartite graph on n+n vertices is such that the mixing time of any markov chain asymptotically uniform on its k-colorings is exponential in n/k^2 (if it is allowed to only change the colors of O(n/k) vertices in a single transition step). This kind of exponential time mixing is called \emphtorpid mixing. As a corollary, we show that there are (for every n) bipartite graphs on 2n vertices with Δ (G) = Ω (\ln n) such that for every k, 6 ≤ k ≤ Δ /(6 \ln Δ ), each member of a large class of chains mixes torpidly. While, for fixed k, such negative results are implied by the work of CDF, our results are more general in that they allow k to grow with n. We also show that these negative results hold true for H-colorings of bipartite graphs provided H contains a spanning complete bipartite subgraph. We also present explicit examples of colorings (k-colorings or H-colorings) which admit 1-cautious chains that are ergodic and are shown to have exponential mixing time. While, for fixed k or fixed H, such negative results are implied by the work of CDF, our results are more general in that they allow k or H to vary with n.
3. A survey of multivariate aspects of the contraction method
We survey multivariate limit theorems in the framework of the contraction method for recursive sequences as arising in the analysis of algorithms, random trees or branching processes. We compare and improve various general conditions under which limit laws can be obtained, state related open problems and give applications to the analysis of algorithms and branching recurrences.
4. Recognizing HH-free, HHD-free, and Welsh-Powell Opposition Graphs
In this paper, we consider the recognition problem on three classes of perfectly orderable graphs, namely, the HH-free, the HHD-free, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in O(n min \m α (n,n), m + n^2 log n\) time whether a given graph G on n vertices and m edges contains a house or a hole; this implies an O(n min \m α (n,n), m + n^2 log n\)-time and O(n+m)-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement øverlineG of the graph G is HH-free can be efficiently resolved in O(n m) time using O(n^2) space, which leads to an O(n m)-time and O(n^2)-space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required O(n^3) time and O(n^2) space.
5. Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infinite triangular mesh is an induced subgraph of the fourth power of the infinite square mesh and we present 2-approximation algorithms for multicoloring a power square mesh and the second power of a triangular mesh, 3-approximation algorithms for multicoloring powers of semi-toroidal meshes and of triangular meshes and 4-approximation algorithm for multicoloring the power of a toroidal mesh. We also give similar algorithms for the Cartesian product of powers of paths and of cycles.
6. P6- and triangle-free graphs revisited: structure and bounded clique-width
The Maximum Weight Stable Set (MWS) Problem is one of the fundamental problems on graphs. It is well-known to be NP-complete for triangle-free graphs, and Mosca has shown that it is solvable in polynomial time when restricted to P6- and triangle-free graphs. We give a complete structure analysis of (nonbipartite) P6- and triangle-free graphs which are prime in the sense of modular decomposition. It turns out that the structure of these graphs is extremely simple implying bounded clique-width and thus, efficient algorithms exist for all problems expressible in terms of Monadic Second Order Logic with quantification only over vertex predicates. The problems Vertex Cover, MWS, Maximum Clique, Minimum Dominating Set, Steiner Tree, and Maximum Induced Matching are among them. Our results improve the previous one on the MWS problem by Mosca with respect to structure and time bound but also extends a previous result by Fouquet, Giakoumakis and Vanherpe which have shown that bipartite P6-free graphs have bounded clique-width. Moreover, it covers a result by Randerath, Schiermeyer and Tewes on polynomial time 3-colorability of P6- and triangle-free graphs.
7. Generalized connected domination in graphs
As a generalization of connected domination in a graph G we consider domination by sets having at most k components. The order γ _c^k (G) of such a smallest set we relate to γ _c(G), the order of a smallest connected dominating set. For a tree T we give bounds on γ _c^k (T) in terms of minimum valency and diameter. For trees the inequality γ _c^k (T)≤ n-k-1 is known to hold, we determine the class of trees, for which equality holds.
8. A Cartesian closed category of event structures with quotients
We introduce a new class of morphisms for event structures. The category obtained is cartesian closed, and a natural notion of quotient event structure is defined within it. We study in particular the topological space of maximal configurations of quotient event structures. We introduce the compression of event structures as an example of quotient: the compression of an event structure E is a minimal event structure with the same space of maximal configurations as E.
9. d-records in geometrically distributed random variables
We study d-records in sequences generated by independent geometric random variables and derive explicit and asymptotic formulæ for expectation and variance. Informally speaking, a d-record occurs, when one computes the d-largest values, and the variable maintaining it changes its value while the sequence is scanned from left to right. This is done for the "strict model," but a "weak model" is also briefly investigated. We also discuss the limit q → 1 (q the parameter of the geometric distribution), which leads to the model of random permutations.
10. Counting l-letter subwords in compositions
Let ℕ be the set of all positive integers and let A be any ordered subset of ℕ. Recently, Heubach and Mansour enumerated the number of compositions of n with m parts in A that contain the subword τ exactly r times, where τ∈{111,112,221,123}. Our aims are (1) to generalize the above results, i.e., to enumerate the number of compositions of n with m parts in A that contain an ℓ-letter subword, and (2) to analyze the number of compositions of n with m parts that avoid an ℓ-letter pattern, for given ℓ. We use tools such as asymptotic analysis of generating functions leading to Gaussian asymptotic.
11. Some new optimal and suboptimal infinite families of undirected double-loop networks
Let n, s be positive integers such that 2 ≤ s < n and s = n/2 . An undirected double-loop network G(n; 1, s) is an undirected graph (V,E), where V =Zn={0, 1, 2, . . . , n−1} and E={(i, i+1 (mod n)), (i, i+s (mod n)) | i ∈ Z}. It is a circulant graph with n nodes and degree 4. In this paper, the sufficient and necessary conditions for a class of undirected double-loop networks to be optimal are presented. By these conditions, 6 new optimal and 5 new suboptimal infinite families of undirected double-loop networks are given.
12. The Online Specialization Problem
We study the online specialization problem, where items arrive in an online fashion for processing by one of n different methods. Each method has two costs: a processing cost (paid once for each item processed), and a set-up cost (paid only once, on the method's first use). There are n possible types of items; an item's type determines the set of methods available to process it. Each method has a different degree of specialization. Highly specialized methods can process few item types while generic methods may process all item types. This is a generalization of ski-rental and closely related to the capital investment problem of Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi, and A. Rosen. On capital investment. In Algorithmica, 25(1):22-36, 1999.. We primarily study the case where method i+1 is always more specialized than method i and the set-up cost for a more specialized method is always higher than that of a less specialized method. We describe an algorithm with competitive ratio O(log(n)), and also show an Ω (log(n)) lower bound on the competitive ratio for this problem; this shows our ratio is tight up to constant factors.
13. On randomly colouring locally sparse graphs
We consider the problem of generating a random q-colouring of a graph G=(V,E). We consider the simple Glauber Dynamics chain. We show that if for all v ∈ V the average degree of the subgraph H_v induced by the neighbours of v ∈ V is #x226a Δ where Δ is the maximum degree and Δ >c_1\ln n then for sufficiently large c_1, this chain mixes rapidly provided q/Δ >α , where α #x2248 1.763 is the root of α = e^\1/α \. For this class of graphs, which includes planar graphs, triangle free graphs and random graphs G_\n,p\ with p #x226a 1, this beats the 11Δ /6 bound of Vigoda for general graphs.
14. Optimal L(h,k)-Labeling of Regular Grids
The L(h, k)-labeling is an assignment of non negative integer labels to the nodes of a graph such that 'close' nodes have labels which differ by at least k, and 'very close' nodes have labels which differ by at least h. The span of an L(h,k)-labeling is the difference between the largest and the smallest assigned label. We study L(h, k)-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The L(h,k)-labeling problem has been intensively studied in some special cases, i.e. when k=0 (vertex coloring), h=k (vertex coloring the square of the graph) and h=2k (radio- or λ -coloring) but no results are known in the general case for regular grids. In this paper, we completely solve the L(h,k)-labeling problem on regular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds.
15. Common intervals in permutations
An interval of a permutation is a consecutive substring consisting of consecutive symbols. For example, 4536 is an interval in the permutation 71453682. These arise in genetic applications. For the applications, it makes sense to generalize so as to allow gaps of bounded size δ -1, both in the locations and the symbols. For example, 4527 has gaps bounded by 1 (since 3 and 6 are missing) and is therefore a δ -interval of 389415627 for δ =2. After analyzing the distribution of the number of intervals of a uniform random permutation, we study the number of 2-intervals. This is exponentially large, but tightly clustered around its mean. Perhaps surprisingly, the quenched and annealed means are the same. Our analysis is via a multivariate generating function enumerating pairs of potential 2-intervals by size and intersection size.\par
16. The first descent in samples of geometric random variables and permutations
For words of length n, generated by independent geometric random variables, we study the average initial and end heights of the first descent in the word. In addition we compute the average initial and end height of the first descent for a random permutation of n letters.
17. On the number of spanning trees of K_n^m #x00B1 G graphs
The K_n-complement of a graph G, denoted by K_n-G, is defined as the graph obtained from the complete graph K_n by removing a set of edges that span G; if G has n vertices, then K_n-G coincides with the complement øverlineG of the graph G. In this paper we extend the previous notion and derive determinant based formulas for the number of spanning trees of graphs of the form K_n^m #x00b1 G, where K_n^m is the complete multigraph on n vertices with exactly m edges joining every pair of vertices and G is a multigraph spanned by a set of edges of K_n^m; the graph K_n^m + G (resp. K_n^m - G) is obtained from K_n^m by adding (resp. removing) the edges of G. Moreover, we derive determinant based formulas for graphs that result from K_n^m by adding and removing edges of multigraphs spanned by sets of edges of the graph K_n^m. We also prove closed formulas for the number of spanning tree of graphs of the form K_n^m #x00b1 G, where G is (i) a complete multipartite graph, and (ii) a multi-star graph. Our results generalize previous results and extend the family of graphs admitting formulas for the number of their spanning trees.
18. On the computability of the topological entropy of subshifts
We prove that the topological entropy of subshifts having decidable language is uncomputable in the following sense: For no error bound less than 1/4 does there exists a program that, given a decision procedure for the language of a subshift as input, will approximate the entropy of the subshift within the error bound. In addition, we prove that not only is the topological entropy of sofic shifts computable to arbitary precision (a well-known fact), but all standard comparisons of the topological entropy with rational numbers are decidable.
19. Tiling Z² with translations of one set
Let A be a finite subset of ℤ2. We say A tiles ℤ2 with the translation set C, if any integer z∈ℤ2 can be represented as z1+z2, z1∈ A, z2∈ C in an unique way. In this case we call A a ℤ2-tile and write A ⊕ C = ℤ2. A tile A is said to be a normal ℤ2-tile if there exists a periodic set C such that A ⊕ C = ℤ2. We characterize all normal ℤ2-tiles with prime cardinality.