Multi-sources simultaneous communication in the wireless mobility model is NP-complete

• Main Authors: Pattama Longani, Nopadon Juneam, Sanpawat Kantabutra
• Format: Journal
• Published: 2018
• Subjects: Biochemistry, Genetics and Molecular Biology; Chemistry; Materials Science; Mathematics; Physics and Astronomy
• Online Access: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84992166193&origin=inward; http://cmuir.cmu.ac.th/jspui/handle/6653943832/55135
• Institution: Chiang Mai University

© 2016, Chiang Mai University. All rights reserved. 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 {s1s′1}, {s2,s′2},…,{sk,s′k}, and a time t ∈ 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.