A GENERAL FRAMEWORK FOR VERTEX ORDERINGS WITH APPLICATIONS TO CIRCUITCLUSTERING

Vertex orderings have been successfully applied to problems in netlist clustering and for system partitioning and layout [2], [20], We prese nt a vertex ordering construction that encompasses most reasonable gra ph traversals, Two parameters-an attraction function and a window-prov ide the means for achieving various graph traversals and addressing pa rticular clustering requirements, We then use dynamic programming [2] to optimally split the vertex ordering into a multiway clustering, Our approach outperforms several clustering methods in the literature in terms of three distinct clustering objectives [5], [8], [22], The orde ring construction, by itself, also outperforms existing graph ordering constructions [2], [13], [17], [19], for this application, Tuning our approach to ''meta-objectives,'' particularly clustering for two-phas e Fiduccia-Mattheyses bipartitioning [9], remains an open area of rese arch.