Technical Report 225-1989

Title

alpha-Vertex-Separation is NP-hard even for 3-regular Graphs

Authors

Rudolf Müller and Dorothea Wagner

Publication

COMPUTING, vol. 46, 1991, pp. 343-353

extended abstract in Methods of Operations Research 62 (1990), pp. 291-293)

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

Two discrete optimization problems arising in VLSI are to reduce the area of a programmable logic array (PLA) and to separate graphs uniformly. We show that a commonly used area reduction technique called blockfolding is equivalent to separating graphs by vertex delition. The later problem is shown to be NP-complete even for 3-regular-graphs.