|
|||||
 |
|
|
|
|
|
|
|
Minimum length
corridor problem on grids
Sogol Jahanbekam, Sindhu Ramu and Elham Sohrabi |
|
Vol. 18 (2025), No. 4, 665–682
|
Abstract |
|
Let be a rectangle that is decomposed into subrectangles. A corridor of is a tree whose edges belong to , where has a vertex in the outer boundary and in each of the subrectangles in . A minimum-length corridor (MLC) is a corridor with the smallest length sum over its edges. In this paper, we determine the minimum-length corridor of the rectangles that are subdivided by horizontal and vertical lines into smaller rectangles (grids) when all horizontal (or vertical) line segments have the same length and the rest of the line segments have a length of at least . We also determine an upper bound for the minimum-length corridor of the grids when all horizontal (or vertical) line segments have the same length and the rest of line segments have length at most . We conclude with a conjecture that the upper bound is tight for some cases. |
Keywords
trees, geometric aspects of graph theory, applications of
graph theory, tiling
|
Mathematical Subject Classification
Primary: 05B45, 05C05, 05C09, 05C90
|
Milestones
Received: 7 September 2023
Revised: 28 February 2024
Accepted: 6 March 2024
Published: 30 July 2025
Communicated by Joshua Cooper
|
Authors |
| Sogol Jahanbekam | |
| Department of Mathematics and
Statistics San Jose State University San Jose, CA United States |
|
| Sindhu Ramu | |
| Department of Mathematics and
Statistics San Jose State University San Jose, CA United States |
|
| Elham Sohrabi | |
| Division of Mathematics and Computer
Science University of South Carolina Upstate Spartanburg, SC United States |
|
| © 2025 MSP (Mathematical Sciences Publishers). |
