Results 61 to 70 of about 1,392 (94)
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
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
Sketching Cuts in Graphs and Hypergraphs [PDF]
, 2014 Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that $(1-\epsilon)$-approximation for Max-Cut must use $n^{1-O(\epsilon)}$ space; moreover, beating $4/5 ...
Kogan, Dmitry, Krauthgamer, Robert
core
The Diameter of the Minimum Spanning Tree of a Complete Graph [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 Let $X_1,\ldots,X_{n\choose 2}$ be independent identically distributed weights for the edges of $K_n$. If $X_i \neq X_j$ for$ i \neq j$, then there exists a unique minimum weight spanning tree $T$ of $K_n$ with these edge weights.
Louigi Addario-Berry +2 more
doaj +1 more source
On the Ehrenfeucht-Mycielski Balance Conjecture [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 In 1992, A. Ehrenfeucht and J. Mycielski defined a seemingly pseudorandom binary sequence which has since been termed the EM-sequence. The balance conjecture for the EM-sequence, still open, is the conjecture that the sequence of EM-sequence initial ...
John C. Kieffer, W. Szpankowski
doaj +1 more source
The Query-commit Problem [PDF]
, 2011 In the query-commit problem we are given a graph where edges have distinct probabilities of existing. It is possible to query the edges of the graph, and if the queried edge exists then its endpoints are irrevocably matched.
Molinaro, Marco, Ravi, R.
core
Stokes polyhedra for $X$-shaped polyminos [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 Consider a pair of $\textit{interlacing regular convex polygons}$, each with $2(n + 2)$ vertices, which we will be referring to as $\textit{red}$ and $\textit{black}$ ones.
Yu. Baryshnikov +3 more
doaj +1 more source
Hyperbolicity, degeneracy, and expansion of random intersection graphs
, 2017 We establish the conditions under which several algorithmically exploitable structural features hold for random intersection graphs, a natural model for many real-world networks where edges correspond to shared attributes.
Farrell, Matthew +5 more
core +1 more source
Space-Efficient DFS and Applications: Simpler, Leaner, Faster
, 2018 The problem of space-efficient depth-first search (DFS) is reconsidered. A particularly simple and fast algorithm is presented that, on a directed or undirected input graph $G=(V,E)$ with $n$ vertices and $m$ edges, carries out a DFS in $O(n+m)$ time ...
Hagerup, Torben
core
From Finite Automata to Regular Expressions and Back--A Summary on Descriptional Complexity
, 2014 The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower
Gruber, Hermann, Holzer, Markus
core +2 more sources