Technical Report CS-2011-05

Title: Some NP-complete problems on graphs
Authors: Fanica Gavril
Abstract: A paper published in a 1977 Conference and very difficult to find.

In this paper we add a number of new graph problems to the long list of the known NP-complete problems. Among them are the Optimal linear cut arrangement, Optimal directed tree arrangement and arrangements on a grid.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2011
To the main CS technical reports page

Computer science department, Technion