The graph search based approaches, such as the directed relation graph (DRG) and DRG with error propagation (DRGEP) methods, are efficient as the first-cut reduction for large detailed chemical mechanisms. In this study, the DRGEP-based methods are further improved by using a Jacobian for evaluating direct interaction coefficient (DIC). Both the Dijkstra's algorithm and the AStar algorithm are studied to assess the effect of graph search algorithms on the performance of DIC using the Jacobian implementation. Additionally, the target search algorithm (TSA) is used for exploring the further reduction potential by initializing with the skeletal mechanisms generated by the graph search methods. High temperature methane and low temperature n-heptane auto-ignition are selected as the testing conditions. For methane with high temperature conditions, the Jacobian DIC with the AStar algorithm has the best performance with 31% species less compared to the previously defined DIC with the Dijkstra's algorithm for the 10% limited error. By restarting TSA initialized with the skeletal mechanisms generated by graph search methods and TSA, an identical 19-species skeletal mechanism is generated. For n-heptane with NTC region conditions, the Jacobian DIC enhances both the two graph search algorithms as well as the methane skeletal reduction. With the combination of the proposed Jacobian DIC and the AStar algorithm, the n-heptane skeletal mechanism generated by repeatedly restarting TSA is 16% smaller (similar to 20 species less) than the one purely developed from multi-round TSA for the 10% error. The validation of n-heptane laminar flame speed against detailed mechanism shows that the skeletal mechanisms developed by the DRGEP-based approaches can retain the chemistry of laminar flames by targeting only 30 cases near NTC regions. (C) 2016 The Combustion Institute. Published by Elsevier Inc. All rights reserved.