Results 51 to 60 of about 1,392 (94)
Analysis of a new skip list variant [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 For a skip list variant, introduced by Cho and Sahni, we analyse what is the analogue of horizontal plus vertical search cost in the original skip list model.
Guy Louchard, Helmut Prodinger
doaj +1 more source
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
, 2015 In runtime verification, the central problem is to decide if a given program execution violates a given property. In online runtime verification, a monitor observes a program’s execution as it happens.
A Bauer +14 more
core +2 more sources
Explicit computation of the variance of the number of maxima in hypercubes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We present a combinatorial approach of the variance for the number of maxima in hypercubes. This leads to an explicit expression, in terms of Multiple Zeta Values, of the dominant term in the asymptotic expansion of this variance.Moreover, we get an ...
Christian Costermans, Hoang Ngoc Minh
doaj +1 more source
Shared-memory Graph Truss Decomposition
, 2017 We present PKT, a new shared-memory parallel algorithm and OpenMP implementation for the truss decomposition of large sparse graphs. A k-truss is a dense subgraph definition that can be considered a relaxation of a clique. Truss decomposition refers to a
Kabir, Humayun, Madduri, Kamesh
core +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
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
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
, 2023 We abstract and study \emph{reachability preservers}, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph $G = (V, E)$ and a set of \emph{demand pairs} $P \subseteq V \times V$, a reachability ...
Abboud, Amir, Bodwin, Greg
core
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