Polynomial Time Efficient Construction Heuristics for Vertex Separation Minimization Problem

Pallavi Jain, Gur Saran, Kamal Srivastava

Vertex Separation Minimization Problem (VSMP) consists of finding a layout of a graph G = (V,E) which minimizes the maximum vertex cut or separation of a layout. It is an NP-comple…