|
|
|
|
Steklov Institute St. Petersburg
|
Technische Universität München
|
State University St. Petersburg
|
Joint Advanced Student School (JASS)
Course 1: Complexity Analysis of String Algorithms
St. Petersburg - Sunday, March 28 through Wednesday, April 7, 2004
Anton Nesterov
Greedy Algorithms for the Shortest Common Superstring Problem
Abstract
This paper is based on a article by A. Frieze and W.Szpankowski. It presents
some greedy algorithms that solve Shortest Common Superstring Problem and
their analysis in probabylistic framework. Also graph algorithms for equivalent problems
are presented.
|
