An NP-Hard Crossing Minimization Problem for Computer Network Layout.

Simple item page
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorKashiwabara, Toshinobuen_US
dc.contributor.authorNakajima, Kazuoen_US
dc.contributor.authorFujisawa, Toshioen_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:36:05Z
dc.date.available2007-05-23T09:36:05Z
dc.date.issued1986en_US
dc.description.abstractA layout problem of computer communication network is formulated graph-theoretically as follows: "Given a simple graph G = (V,E), find an embedding of G with the minimum number of edge-crossings such that (i) the vertices in V are placed on the circumference of a circle C, and (ii) the edges in E are drawn only inside C." In this paper, this problem will be shown to be NP-hard. Therefore, it is very likely to be intractable.en_US
dc.format.extent976833 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4503
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1986-80en_US
dc.titleAn NP-Hard Crossing Minimization Problem for Computer Network Layout.en_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_86-80.pdf
Size:
953.94 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports