Results 31 to 40 of about 1,392 (94)
Conditioned Galton-Watson trees do not grow [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 An example is given which shows that, in general, conditioned Galton-Watson trees cannot be obtained by adding vertices one by one, while this can be done in some important but special cases, as shown by Luczak and Winkler.
Svante Janson
doaj +1 more source
The $p$-Center Problem in Tree Networks Revisited [PDF]
, 2016 We present two improved algorithms for weighted discrete $p$-center problem for tree networks with $n$ vertices. One of our proposed algorithms runs in $O(n \log n + p \log^2 n \log(n/p))$ time.
Banik, Aritra +4 more
core +2 more sources
An extension to overpartitions of Rogers-Ramanujan identities for even moduli [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We investigate class of well-poised basic hypergeometric series $\tilde{J}_{k,i}(a;x;q)$, interpreting these series as generating functions for overpartitions defined by multiplicity conditions.
Sylvie Corteel +2 more
doaj +1 more source
Statistical Properties of Similarity Score Functions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 In computational biology, a large amount of problems, such as pattern discovery, deals with the comparison of several sequences (of nucleotides, proteins or genes for instance).
Jérémie Bourdon, Alban Mancheron
doaj +1 more source
Spanning trees of finite Sierpiński graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We show that the number of spanning trees in the finite Sierpiński graph of level $n$ is given by $\sqrt[4]{\frac{3}{20}} (\frac{5}{3})^{-n/2} (\sqrt[4]{540})^{3^n}$.
Elmar Teufl, Stephan Wagner
doaj +1 more source
Combinatorial Dominance Guarantees for Heuristic Algorithms [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 An $f(n)$ $\textit{dominance bound}$ on a heuristic for some problem is a guarantee that the heuristic always returns a solution not worse than at least $f(n)$ solutions.
Daniel Berend +2 more
doaj +1 more source
Matching solid shapes in arbitrary dimension via random sampling [PDF]
Discrete Mathematics & Theoretical Computer Science, 2012 We give simple probabilistic algorithms that approximately maximize the volume of overlap of two solid, i.e. full-dimensional, shapes under translations and rigid motions. The shapes are subsets of $ℝ^d$ where $d≥ 2$.
Daria Schymura
doaj +1 more source
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs [PDF]
, 2016 We present space-efficient algorithms for computing cut vertices in a given graph with $n$ vertices and $m$ edges in linear time using $O(n+\min\{m,n\log \log n\})$ bits.
Kammer, Frank +2 more
core +2 more sources
Constructions for Clumps Statistics. [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 We consider a component of the word statistics known as clump; starting from a finite set of words, clumps are maximal overlapping sets of these occurrences. This object has first been studied by Schbath with the aim of counting the number of occurrences
Frédérique Bassino +3 more
doaj +1 more source
Literature survey on low rank approximation of matrices
, 2016 Low rank approximation of matrices has been well studied in literature. Singular value decomposition, QR decomposition with column pivoting, rank revealing QR factorization (RRQR), Interpolative decomposition etc are classical deterministic algorithms ...
Kumar, N. Kishore, Shneider, Jan
core +1 more source