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 |
| Summary: | © 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. |
|---|