Results 41 to 50 of about 215 (72)
Accessible and Deterministic Automata: Enumeration and Boltzmann Samplers [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We present a bijection between the set $\mathcal{A}_n$ of deterministic and accessible automata with $n$ states on a $k$-letters alphabet and some diagrams, which can themselves be represented as partitions of the set $[\![ 1..(kn+1) ]\!]$ into $n$ non ...
Frédérique Bassino, Cyril Nicaud
doaj +1 more source
Discrete Mathematics & Theoretical Computer Science, 2005 We consider the $\textit{master ring problem (MRP)}$ which often arises in optical network design. Given a network which consists of a collection of interconnected rings $R_1, \ldots, R_K$, with $n_1, \ldots, n_K$ distinct nodes, respectively, we need to
Hadas Shachnai, Lisa Zhang
doaj +1 more source
Concentration Properties of Extremal Parameters in Random Discrete Structures [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 The purpose of this survey is to present recent results concerning concentration properties of extremal parameters of random discrete structures. A main emphasis is placed on the height and maximum degree of several kinds of random trees. We also provide
Michael Drmota
doaj +1 more source
Properties of Random Graphs via Boltzmann Samplers [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 This work is devoted to the understanding of properties of random graphs from graph classes with structural constraints. We propose a method that is based on the analysis of the behaviour of Boltzmann sampler algorithms, and may be used to obtain precise
Konstantinos Panagiotou, Andreas Weißl
doaj +1 more source
A coupon collector's problem with bonuses [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 In this article, we study a variant of the coupon collector's problem introducing a notion of a \emphbonus. Suppose that there are c different types of coupons made up of bonus coupons and ordinary coupons, and that a collector gets every coupon with ...
Toshio Nakata, Izumi Kubo
doaj +1 more source
Bipartite Random Graphs and Cuckoo Hashing [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 The aim of this paper is to extend the analysis of Cuckoo Hashing of Devroye and Morin in 2003. In particular we make several asymptotic results much more precise.
Reinhard Kutzelnigg
doaj +1 more source
Randomized Optimization: a Probabilistic Analysis [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 In 1999, Chan proposed an algorithm to solve a given optimization problem: express the solution as the minimum of the solutions of several subproblems and apply the classical randomized algorithm for finding the minimum of $r$ numbers.
Jean Cardinal +2 more
doaj +1 more source
Average depth in a binary search tree with repeated keys [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 Random sequences from alphabet $\{1, \ldots,r\}$ are examined where repeated letters are allowed. Binary search trees are formed from these, and the average left-going depth of the first $1$ is found.
Margaret Archibald, Julien Clément
doaj +1 more source
On the number of decomposable trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 A tree is called $k$-decomposable if it has a spanning forest whose components are all of size $k$. Analogously, a tree is called $T$-decomposable for a fixed tree $T$ if it has a spanning forest whose components are all isomorphic to $T$. In this paper,
Stephan G. Wagner
doaj +1 more source
$S$-constrained random matrices [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 Let $S$ be a set of $d$-dimensional row vectors with entries in a $q$-ary alphabet. A matrix $M$ with entries in the same $q$-ary alphabet is $S$-constrained if every set of $d$ columns of $M$ contains as a submatrix a copy of the vectors in $S$, up to ...
Sylvain Gravier, Bernard Ycart
doaj +1 more source