An Alternative Proof for the NP-completeness of Top Right Access point-Minimum Length Corridor Problem

被引：0

作者：

Priyadarsini, P. L. K. ^{[1
]}

Hemalatha, T. ^{[2
]}

机构：

[1] NIT, Dept Comp Applns, Trichy, Tamil Nadu, India

[2] NIT, Dept Math, Trichy, Tamil Nadu, India

来源：

PROCEEDINGS OF WORLD ACADEMY OF SCIENCE, ENGINEERING AND TECHNOLOGY, VOL 26, PARTS 1 AND 2, DECEMBER 2007 | 2007年 / 26卷

关键词：

NP-complete; 2-Connected planar graph; Grid embedding of a plane graph;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the Top Right Access point Minimum Length Corridor (TRA-MLC) problem [1], a rectangular boundary partitioned into rectilinear polygons is given and the problem is to find a corridor of least total length and it must include the top right corner of the outer rectangular boundary. A corridor is a tree containing a set of line segments lying along the outer rectangular boundary and/or on the boundary of the rectilinear polygons: The corridor must contain at least one point: from the boundaries of the outer rectangle and also the rectilinear polygons. Gutierrez and Gonzalez [1] proved that the MLC problem, along with some of its restricted versions and variants, are NP-complete. In this paper, we give a shorter proof of NP-Completeness of TRA-MLC by findig the reduction in the following way.

引用

页码：468 / +

页数：2