CiteULike: bigbossman's algorithm

The Small-World Phenomenon: An Algorithmic Perspective

Jon Kleinberg — 2005-01-02T16:34:15-00:00

(# 2000)

Long a matter of folklore, the "small-world phenomenon" -- the principle that we are all linked by short chains of acquaintances -- was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960's. This work was among the first to make the phenomenon quantitative, allowing people to speak of the "six degrees of separation" between any two people in the United States. Since then, a number of network models have been proposed as...

Domination in graphs with bounded propagation: algorithms, formulations and hardness results

Ashkan Aazami — 2008-02-18T15:46:39-00:00

(15 Feb 2008)

We introduce a hierarchy of problems between the \textscDominating Set problem and the \textscPower Dominating Set (PDS) problem called the $\ell$-round power dominating set ($\ell$-round PDS, for short) problem. For $\ell=1$, this is the \textscDominating Set problem, and for $\ell≥ n-1$, this is the PDS problem; here $n$ denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes $S$ that power dominates all the nodes, where a node $v$ is power dominated if (1) $v$ is in $S$ or it has a neighbor in $S$, or (2) $v$ has a neighbor $u$ such that $u$ and all of its neighbors except $v$ are power dominated. Note that rule (1) is the same as for the \textscDominating Set problem, and that rule (2) is a type of propagation rule that applies iteratively. The $\ell$-round PDS problem has the same set of rules as PDS, except we apply rule (2) in “parallel” in at most $\ell-1$ rounds. We prove that $\ell$-round PDS cannot be approximated better than $2^\log^1-εn$ even for $\ell=4$ in general graphs. We provide a dynamic programming algorithm to solve $\ell$-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation scheme) for $\ell$-round PDS on planar graphs for $\ell=O(\tfrac\logn\log\logn)$. Finally, we give integer programming formulations for $\ell$-round PDS.

A decentralized algorithm for spectral analysis

David Kempe — 2006-05-07T20:15:24-00:00

(2004), pp. 561-568.

An Optimal Algorithm for Generating Minimal Perfect Hash Functions

Zbigniew Czech — 2007-12-06T03:04:54-00:00

Information Processing Letters, Vol. 43, No. 5. (1992), pp. 257-264.

A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice. Keywords: Data structures, probabilistic algorithms, analysis of algorithms, hashing, random graphs

A Polynominal Time Algorithm for Graph Isomorphism

Reiner Czerwinski — 2007-11-14T04:51:00-00:00

(13 Nov 2007)

Algorithms testing two graphs for isomorphism known as yet have exponential worst case complexity. In this paper we propose a new algorithm that has polynomial complexity and constructively supplies the evidence that the graph isomorphism lies in P.

A fast multilevel algorithm for graph clustering and community detection

Hristo Djidjev — 2007-07-18T12:38:22-00:00

(16 Jul 2007)

One of the most useful measures of cluster quality is the modularity of a partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random (unstructured) graph. In this paper we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut problem on a complete graph with the same vertices as G. We then show that the resulted minimum cut problem can be efficiently solved with existing software for graph partitioning and that our algorithm finds clusterings of a better quality and much faster than the existing clustering algorithms.

Fast discovery of connection subgraphs

Christos Faloutsos — 2005-07-05T18:44:22-00:00

(2004), pp. 118-127.

Algorithmic aspects of bandwidth trading

Randeep Bhatia — 2007-02-20T21:26:39-00:00

ACM Trans. Algorithms, Vol. 3, No. 1. (February 2007)

Market Equilibrium via a Primal-Dual-Type Algorithm

N Devanur — 2006-11-26T22:52:15-00:00

(2002)

Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear version of a problem defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn's primaldual algorithm for bipartite matching.