Multi-sources simultaneous communication in the wireless mobility model is NP-complete
© 2014 IEEE. In this article we consider a mobility model M=(S, D, U, L, R, V, C, O), where S is a set of sources, D a set of directions, U a set of users, L a set of user movements, R a set of source movements, V a set of velocities of sources, C a set of source coverages, and O a set of obstacles....
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
2015
|
| Online Access: | http://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=84911877323&origin=inward http://cmuir.cmu.ac.th/handle/6653943832/39253 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| Summary: | © 2014 IEEE. In this article we consider a mobility model M=(S, D, U, L, R, V, C, O), where S is a set of sources, D a set of directions, U a set of users, L a set of user movements, R a set of source movements, V a set of velocities of sources, C a set of source coverages, and O a set of obstacles. Particularly, we study a problem called MULTI-SOURCES SIMULTANEOUS COMMUNICATION PROBLEM in this model. This problem is stated as follows: given a mobility model M=(S, D, U, L, R, V, C, O), k pairs of distinct sources s1, s′1, s2, s′2,...,sk, s′k, and a time t, can all k pairs of sources simultaneously communicate throughout the duration t of the model without sharing a source? We show that the complexity of this problem is at least as hard as the ONE-IN-THREE 3-SATISFIABILITY unless P=NP. |
|---|