閱讀全文 | |
篇名 |
On Phalanx Graph Search Number
|
---|---|
並列篇名 | On Phalanx Graph Search Number |
作者 | Ondrej 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. |
起訖頁 | 1189-1198 |
關鍵詞 | Phalanx graph searching、Connected graph searching、Spanning tree |
刊名 | 網際網路技術學刊 |
期數 | 202007 (21:4期) |
出版單位 | 台灣學術網路管理委員會 |
DOI |
|
QR Code | |
該期刊 上一篇
| An Improved ICP with Heuristic Initial Pose for Point Cloud Alignment |
該期刊 下一篇
| Exact and Heuristic Algorithms for Some Spatial-aware Interest Group Query Problems |