---
title: "Search in a Small World"
authors:
  - "Toby Walsh"
doi: ""
url: "https://ijcai.org/proceedings/1999/166"
pdf: "https://ijcai.org/proceedings/1999/0166.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "1172-1176"
track: "Search"
keywords:
---

# Search in a Small World

Toby Walsh

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, pages 1172-1176.

## Abstract

In a graph with a "small world" topology, nodes are highly clustered yet the path length between them is small. Such a topology can make search problems very difficult since local decisions quickly propagate globally. We show that graphs a<>sociated with many different search problems have a small world topology, and that the cost of solving such search problems can have a heavy-tailed distribution. The strategy of randomization and restarts appears to eliminate these heavy tails. A novel restart schedule in which the cutoff bound is increased geometrically appears particularly effective.