Abstract: To reduce the runtime for clock skew scheduling,a novel near-linear time approach is proposed.The key part of this approach is a clock skew scheduling algorithm which uses integers to measure delay.By requiring the increment of the clock latency to be at least one at each iteration,the time complexity can be reduced.This approach also changes the traditional flow which generates the full sequential graph as the input for clock skew scheduling algorithms.Instead,a novel incremental delay extraction method is used to extract only the weights of critical arcs for clock skew scheduling algorithms.Thus the runtime for generating the sequential graph is reduced.Experimental results show that the runtimes of our algorithms are only tens of seconds for benchmarks with thousands of flip-flops.