### Abstract

Researchers in recent years have developed many graph algorithms that are fast in the worst case, but little work has been done on graph algorithms that are fast on the average. (Exceptions include the work of Angluin and Valiant [1], Karp [7], and Schnorr [9].) In this paper we analyze the expected running time of four algorithms for solving graph connectivity problems. Our goal is to exhibit algorithms whose expected time is within a constant factor of optimum and to shed light on the properties of random graphs,

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980 |

Publisher | Association for Computing Machinery |

Pages | 368-377 |

Number of pages | 10 |

ISBN (Electronic) | 0897910176 |

DOIs | |

State | Published - Apr 28 1980 |

Externally published | Yes |

Event | 12th Annual ACM Symposium on Theory of Computing, STOC 1980 - Los Angeles, United States Duration: Apr 28 1980 → Apr 30 1980 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 1980-April |

ISSN (Print) | 0737-8017 |

### Other

Other | 12th Annual ACM Symposium on Theory of Computing, STOC 1980 |
---|---|

Country | United States |

City | Los Angeles |

Period | 4/28/80 → 4/30/80 |

### All Science Journal Classification (ASJC) codes

- Software

## Cite this

Karp, R. M., & Tarjan, R. E. (1980). Linear expected-time algorithms for connectivity problems. In

*Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980*(pp. 368-377). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 1980-April). Association for Computing Machinery. https://doi.org/10.1145/800141.804686