Results 41 to 50 of about 1,392 (94)
Relative Worst-Order Analysis: A Survey [PDF]
, 2018 Relative worst-order analysis is a technique for assessing the relative quality of online algorithms. We survey the most important results obtained with this technique and compare it with other quality measures.Comment: 20 ...
A Borodin +53 more
core +2 more sources
Samples of geometric random variables with multiplicity constraints [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We investigate the probability that a sample $\Gamma=(\Gamma_1,\Gamma_2,\ldots,\Gamma_n)$ of independent, identically distributed random variables with a geometric distribution has no elements occurring exactly $j$ times, where $j$ belongs to a specified
Margaret Archibald, Arnold Knopfmacher
doaj +1 more source
Truss Decomposition in Massive Networks [PDF]
, 2012 The k-truss is a type of cohesive subgraphs proposed recently for the study of networks. While the problem of computing most cohesive subgraphs is NP-hard, there exists a polynomial time algorithm for computing k-truss. Compared with k-core which is also
Cheng, James, Wang, Jia
core +2 more sources
Structure of Stable Sand Piles Model [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 In this paper we study a variant of the Sand Piles Model, where the evolution rule consists of the falling down of one grain to a random column and an avalanche to reach a stable configuration.
Thi Ha Duong Phan, Thi Thu Huong Tran
doaj +1 more source
Density of truth in modal logics [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 The aim of this paper is counting the probability that a random modal formula is a tautology. We examine $\{ \to,\Box \}$ fragment of two modal logics $\mathbf{S5}$ and $\mathbf{S4}$ over the language with one propositional variable.
Zofia Kostrzycka
doaj +1 more source
Grafalgo - A Library of Graph Algorithms and Supporting Data Structures (revised) [PDF]
, 2015 This report provides an (updated) overview of {\sl Grafalgo}, an open-source library of graph algorithms and the data structures used to implement them.
Turner, Jonathan
core +3 more sources
K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases [PDF]
, 2008 We consider the $k$-core decomposition of network models and Internet graphs at the autonomous system (AS) level. The $k$-core analysis allows to characterize networks beyond the degree distribution and uncover structural properties and hierarchies due ...
Alvarez-Hamelin, José Ignacio +3 more
core +3 more sources
Linear time recognition of P4-indifference graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has ...
Michel Habib +2 more
doaj +1 more source
Extracting the hierarchical organization of complex systems
, 2007 Extracting understanding from the growing ``sea'' of biological and socio-economic data is one of the most pressing scientific challenges facing us.
A. A. Moreira +21 more
core +2 more sources
Exploiting non-constant safe memory in resilient algorithms and data structures [PDF]
, 2015 We extend the Faulty RAM model by Finocchi and Italiano (2008) by adding a safe memory of arbitrary size $S$, and we then derive tradeoffs between the performance of resilient algorithmic techniques and the size of the safe memory.
DE STEFANI, LORENZO +1 more
core +2 more sources