Journal Volumes


Visitors
ALL : 2,334,994
TODAY : 6,248
ONLINE : 227

  JOURNAL DETAIL



Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete


Paper Type 
Contributed Paper
Title 
Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete
Author 
Pattama Longani [a], Nopadon Juneam [b], Sanpawat Kantabutra*[c]
Email 
sanpawat@alumni.tufts
Abstract:
 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 (MSSCP) 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 e N, 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. In addition, we also give an exact algorithm and a heuristic one for MSSCP and show that if the communication among sources in MSSCP can be represented by a complete bipartite graph, Km,n, then MSSCP can be solved in polynomial time.

Start & End Page 
1205 - 1221
Received Date 
2015-05-20
Revised Date 
Accepted Date 
2016-03-28
Full Text 
  Download
Keyword 
wireless mobility networks, NP-completeness, intractability, bipartite
Volume 
Vol.43 No.5 (OCTOBER 2016)
DOI 
Citation 
Longani P., Juneam N. and Kantabutra S., Multi-sources Silmultanieous Communication in the Wireless Mobility Model is NP-complete, Chiang Mai J. Sci., 2016; 43(5): 1205-1221.
SDGs
View:558 Download:169

  RELATED ARTICLE

The NP-Hardness of the Connected p-Median Problem on Bipartite Graphs and Split Graphs*
page: 83 - 88
Author:Shun-Chieh Chang1, William Chung-Kung Yen2, Yue-Li Wang1, and Jia-Jie Liu2
Vol.40 No.1 (JANUARY 2013) View: 531 Download:188
Algorithmic Results of Independent k-Domination on Weighted Graphs
page: 58 - 70
Author:William C-K. Yen
Vol.38 (SPECIAL ISSUE 2011) View: 598 Download:139



Search in this journal


Document Search


Author Search

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Popular Search






Chiang Mai Journal of Science

Faculty of Science, Chiang Mai University
239 Huaykaew Road, Tumbol Suthep, Amphur Muang, Chiang Mai 50200 THAILAND
Tel: +6653-943-467




Faculty of Science,
Chiang Mai University




EMAIL
cmjs@cmu.ac.th




Copyrights © Since 2021 All Rights Reserved by Chiang Mai Journal of Science