The algorithm of directed relation graph recently developed for skeletal mechanism reduction was extended to overall linear time operation, thereby greatly facilitating the computational effort in mechanism reduction, particularly for those involving large mechanisms. Together with a two-stage reduction strategy and using the kinetic responses of autoignition and perfectly stirred reactor (PSR) with extensive parametric variations as the criteria in eliminating unimportant species, a detailed 561-species n-heptane mechanism and a detailed 857-species iso-octane mechanism were successfully reduced to skeletal mechanisms consisting of 188 and 233 species, respectively. These skeletal mechanisms were demonstrated to mimic well the performance of the detailed mechanisms, not only for the autoignition and PSR systems based on which the reduced mechanisms were developed but also for the independent system of jet-stirred reactor. It was further observed that the accuracy of calculated species concentrations was equivalently bounded by the user-specified error threshold value and that the reduction time for a single reaction state is only about 50 ms for the large iso-octane mechanism. (c) 2005 The Combustion Institute. Published by Elsevier Inc. All rights reserved.