Zig-Zag Numberlink is NP-Complete

Zig-Zag Numberlink is NP-Complete

When can t terminal pairs in an m × n grid be connected by t vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the “cover all vertices” constrai...

Full description

Bibliographic Details
Main Authors: Adcock, Aaron, Reidl, Felix, Demaine, Erik D., Demaine, Martin L., O'Brien, Michael P., Villaamil, Fernando Sanchez, Sullivan, Blair D.
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Information Processing Society of Japan 2015
Online Access:http://hdl.handle.net/1721.1/100008
https://orcid.org/0000-0003-3803-5703

Internet

http://hdl.handle.net/1721.1/100008
https://orcid.org/0000-0003-3803-5703

Similar Items