Complexity of Combinatorial Algorithms
Author:
- Robert Endre TarjanRTRobert Endre Tarjan
- 1 July 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Review
- Vol. 20 (3) , 457-491
Abstract
This paper examines recent Work on the complexity of combinatorial algorithms, highlighting the aims of the work, the mathematical tools used, and the important results. Included are sections discussing ways to measure the complexity of an algorithm, methods for proving that certain problems are very hard to solve, tools useful in the design of good algorithms, and recent improvements in algorithms for solving ten representative problems. The final section suggests some directions for future research.Keywords
This publication has 128 references indexed in Scilit:
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- Linear expected time of a simple union-find algorithmInformation Processing Letters, 1976
- Finding the medianJournal of Computer and System Sciences, 1976
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- General context-free recognition in less than cubic timeJournal of Computer and System Sciences, 1975
- A new algorithm for finding weak componentsInformation Processing Letters, 1974
- A V log V algorithm for isomorphism of triconnected planar graphsJournal of Computer and System Sciences, 1973
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme IMonatshefte für Mathematik, 1931
- Über das UnendlicheMathematische Annalen, 1926