LEDA-SM: Extending LEDA to secondary memory

Abstract. During the last years, many software libraries for in-core computation have been developed. Most internal memory algorithms perform very badly when used in an external memory setting. We intro-duce LEDA-SM that extends the LEDA-library [22] towards secondary memory computation. LEDA-SM uses I/O-ecient algorithms and data structures that do not suer from the so called I/O bottleneck. LEDA is used for in-core computation. We explain the design of LEDA-SM and report on performance results.