Vol. 15 no. 2


1. Descent variation of samples of geometric random variables

Brennan, Charlotte ; Knopfmacher, Arnold.
In this paper, we consider random words ω1ω2ω3⋯ωn of length n, where the letters ωi ∈ℕ are independently generated with a geometric probability such that Pωi=k=pqk-1 where p+q=1 . We have a descent at position i whenever ωi+1 < ωi. The size of such a descent is ωi-ωi+1 and the descent variation is the sum of all the descent sizes for that word. We study various types of random words over the infinite alphabet ℕ, where the letters have geometric probabilities, and find the probability […]
Section: Combinatorics

2. Operations on partially ordered sets and rational identities of type A

Boussicault, Adrien.
We consider the family of rational functions ψw= ∏( xwi - xwi+1 )-1 indexed by words with no repetition. We study the combinatorics of the sums ΨP of the functions ψw when w describes the linear extensions of a given poset P. In particular, we point out the connexions between some transformations on posets and elementary operations on the fraction ΨP. We prove that the denominator of ΨP has a closed expression in terms of the Hasse diagram of P, and we compute its numerator in some special […]
Section: Combinatorics

3. On the enumeration of d-minimal permutations

Bouvel, Mathilde ; Ferrari, Luca.
We suggest an approach for the enumeration of minimal permutations having d descents which uses skew Young tableaux. We succeed in finding a general expression for the number of such permutations in terms of (several) sums of determinants. We then generalize the class of skew Young tableaux under consideration; this allows in particular to discover some presumably new results concerning Eulerian numbers.

4. Efficient repeat finding in sets of strings via suffix arrays

Barenbaum, Pablo ; Becher, Verónica ; Deymonnaz, Alejandro ; Halsband, Melisa ; Heiber, Pablo Ariel.
We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set; (b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring O(m) memory, where m is the length of the longest input string, and O(n &log;m) time, where n is the the whole input size (the sum of the length of each string in the input). The most expensive […]
Section: Discrete Algorithms

5. Bipartite powers of k-chordal graphs

Chandran, Sunil,  ; Mathew, Rogers.
Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is Gm+2. Brandstädt et al. in [Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Mathematics, 177(1-3):9-16, 1997.] showed that if Gm is k-chordal, […]
Section: Graph Theory

6. Connectivity for line-of-sight networks in higher dimensions

Devroye, Luc ; Farczadi, Linda.
Let T be a d-dimensional toroidal grid of n^d points. For a given range parameter ω, and a positive integer k ≤q d, we say that two points in T are mutually visible if they differ in at most k coordinates and are a distance at most ω apart, where distance is measured using the \ellₚ norm. We obtain a random d-dimensional line-of-sight graph G by placing a node at each point in T independently with some fixed probability p^* and connecting all pairs of mutually visible nodes. We prove an […]
Section: Analysis of Algorithms

7. Improved bounds on the crossing number of butterfly network

Manuel, Paul D. ; Rajan, Bharati ; Rajasingh, Indra ; Beulah, P. Vasanthi.
We draw the r-dimensional butterfly network with 1 / 44r+O(r2r) crossings which improves the previous estimate given by Cimikowski (1996). We also give a lower bound which matches the upper bound obtained in this paper.
Section: Graph Theory

8. The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degree

Szymańska, Edyta.
In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c\binom|V(H)|-1r-1, or minimum degree of a pair of vertices at least c\binom|V(H)|-2r-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain first optimal dichotomy results for 2-colorings of r-uniform hypergraphs. For each problem, for every r≥q 3 we determine a threshold value depending on r such that the problem is NP-complete for c […]
Section: Discrete Algorithms

9. Derivatives of approximate regular expressions

Champarnaud, Jean-Marc ; Jeanne, Hadrien ; Mignot, Ludovic.
Our aim is to construct a finite automaton recognizing the set of words that are at a bounded distance from some word of a given regular language. We define new regular operators, the similarity operators, based on a generalization of the notion of distance and we introduce the family of regular expressions extended to similarity operators, that we call AREs (Approximate Regular Expressions). We set formulae to compute the Brzozowski derivatives and the Antimirov derivatives of an ARE, which […]
Section: Automata, Logic and Semantics

10. A stronger recognizability condition for two-dimensional languages

Anselmo, Marcella ; Madonia, Maria.
The paper presents a condition necessarily satisfied by (tiling system) recognizable two-dimensional languages. The new recognizability condition is compared with all the other ones known in the literature (namely three conditions), once they are put in a uniform setting: they are stated as bounds on the growth of some complexity functions defined for two-dimensional languages. The gaps between such functions are analyzed and examples are shown that asymptotically separate them. Finally the new […]
Section: Automata, Logic and Semantics

11. Removable edges in near-bricks

Wang, Xiumei ; He, Cheng ; Lin, Yixun.
For a brick apart from a few small graphs, Lovász (1987) proposed a conjecture on the existence of an edge whose deletion results in a graph with only one brick in its tight cut decomposition. Carvalho, Lucchesi, and Murty (2002) confirmed this conjecture by showing the existence of such two edges. This paper generalizes the result obtained by Carvalho et al. to the case of irreducible near-brick, where a graph is irreducible if it contains no induced odd path of length 3 or more. Meanwhile, a […]
Section: Graph Theory

12. Topological structuring of the digital plane

Šlapal, Josef.
We discuss an Alexandroff topology on ℤ2 having the property that its quotient topologies include the Khalimsky and Marcus-Wyse topologies. We introduce a further quotient topology and prove a Jordan curve theorem for it.
Section: Combinatorics

13. Probe interval graphs and probe unit interval graphs on superclasses of cographs

Bonomo, Flavia ; Durán, Guillermo ; Grippo, Luciano N. ; Safe, Martın D..
A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the […]
Section: Graph Theory

14. On-line ranking of split graphs

Borowiecki, Piotr ; Dereniowski, Dariusz.
A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution […]
Section: Graph and Algorithms

15. Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

Gosselin, Shonda ; Szymański, Andrzej ; Wojda, Adam Pawel.
A \em cyclic q-partition of a hypergraph (V,E) is a partition of the edge set E of the form \F,F^θ,F^θ², \ldots, F^θ^q-1\ for some permutation θ of the vertex set V. Let Vₙ = \ 1,2,\ldots,n\. For a positive integer k, Vₙ\choose k denotes the set of all k-subsets of Vₙ. For a nonempty subset K of V_n-1, we let \mathcalKₙ^(K) denote the hypergraph ≤ft(Vₙ, \bigcup_k∈ K Vₙ\choose k\right). In this paper, we find a necessary and sufficient condition on n, q and k for the existence of a cyclic […]
Section: Combinatorics

16. A note on contracting claw-free graphs

Fiala, Jiří ; Kamiński, Marcin ; Paulusma, Daniël.
A graph containment problem is to decide whether one graph called the host graph can be modified into some other graph called the target graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible graph operations permitted. By allowing any combination of these four operations we capture the following problems: testing on (induced) minors, (induced) topological minors, (induced) subgraphs, (induced) […]
Section: Discrete Algorithms

17. A note on the NP-hardness of two matching problems in induced subgrids

Demange, Marc ; Ekim, Tınaz.
Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out some promising research directions. We also sketch the general framework of a unified approach to show the NP-hardness of some problems in subgrids.
Section: Graph Theory

18. Maximal independent sets in bipartite graphs with at least one cycle

Li, Shuchao ; Zhang, Huihui ; Zhang, Xiaoyan.
A maximal independent set is an independent set that is not a proper subset of any other independent set. Liu [J.Q. Liu, Maximal independent sets of bipartite graphs, J. Graph Theory, 17 (4) (1993) 495-507] determined the largest number of maximal independent sets among all n-vertex bipartite graphs. The corresponding extremal graphs are forests. It is natural and interesting for us to consider this problem on bipartite graphs with cycles. Let \mathscrBₙ (resp. \mathscrBₙ') be the set of all […]
Section: Graph Theory

19. Coupon collecting and transversals of hypergraphs

Wild, Marcel ; Janson, Svante ; Wagner, Stephan ; Laurie, Dirk.
The classic Coupon-Collector Problem (CCP) is generalized. Only basic probability theory is used. Centerpiece rather is an algorithm that efficiently counts all k-element transversals of a set system.
Section: Analysis of Algorithms