On phalanx graph search number
© 2020 Taiwan Academic Network Management Committee. All rights reserved. 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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Journal |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85091334609&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/70445 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| id |
th-cmuir.6653943832-70445 |
|---|---|
| record_format |
dspace |
| spelling |
th-cmuir.6653943832-704452020-10-14T08:31:00Z On phalanx graph search number Ondřej Navrátil Sanpawat Kantabutra Sheng Lung Peng Computer Science © 2020 Taiwan Academic Network Management Committee. All rights reserved. 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. 2020-10-14T08:31:00Z 2020-10-14T08:31:00Z 2020-01-01 Journal 20794029 16079264 2-s2.0-85091334609 10.3966/160792642020072104027 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85091334609&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/70445 |
| institution |
Chiang Mai University |
| building |
Chiang Mai University Library |
| continent |
Asia |
| country |
Thailand Thailand |
| content_provider |
Chiang Mai University Library |
| collection |
CMU Intellectual Repository |
| topic |
Computer Science |
| spellingShingle |
Computer Science Ondřej Navrátil Sanpawat Kantabutra Sheng Lung Peng On phalanx graph search number |
| description |
© 2020 Taiwan Academic Network Management Committee. All rights reserved. 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. |
| format |
Journal |
| author |
Ondřej Navrátil Sanpawat Kantabutra Sheng Lung Peng |
| author_facet |
Ondřej Navrátil Sanpawat Kantabutra Sheng Lung Peng |
| author_sort |
Ondřej Navrátil |
| title |
On phalanx graph search number |
| title_short |
On phalanx graph search number |
| title_full |
On phalanx graph search number |
| title_fullStr |
On phalanx graph search number |
| title_full_unstemmed |
On phalanx graph search number |
| title_sort |
on phalanx graph search number |
| publishDate |
2020 |
| url |
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85091334609&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/70445 |
| _version_ |
1681752904002699264 |