On Phalanx Graph Search Number

Ondřej Navrátil,
Sanpawat Kantabutra,
Sheng-Lung Peng,


We introduce an extension of the Connected Graph Search, called Phalanx Graph Search, which inherently emerges from the nature of certain applications. We discuss its key properties, prove NP-hardness of the problem on general graphs and introduce a linear-time algorithm for the class of trees. We exploit our analysis to examine the Minimum Phalanx Graph Search Spanning Tree Problem, again showing its hardness and investigating efficiency of certain approximations. We discuss some of our findings in relation to other search variants.

Citation Format:
Ondřej Navrátil, Sanpawat Kantabutra, Sheng-Lung Peng, "On Phalanx Graph Search Number," Journal of Internet Technology, vol. 21, no. 4 , pp. 1189-1198, Jul. 2020.

Full Text:



  • There are currently no refbacks.

Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Office of Library and Information Services, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd., Shoufeng, Hualien 974301, Taiwan, R.O.C.
Tel: +886-3-931-7314  E-mail: jit.editorial@gmail.com