The complexity of the overlay network verification and its related problems

© 2014 IEEE. In this paper we introduce a special type of virtual networks called an overlay network. We first study a decision problem called the OVERLAY NETWORK VERIFICATION PROBLEM and show that this problem is NP-complete. We then place some restriction to the original problem and prove that the...

Full description

Saved in:

Bibliographic Details
Main Authors:	Wattana Jindaluang, Sanpawat Kantabutra, Varin Chouvatut
Format:	Conference Proceeding
Published:	2018
Subjects:	Computer Science Mathematics Medicine
Online Access:	https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84942856816&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/53416
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Chiang Mai University

id	th-cmuir.6653943832-53416
record_format	dspace
spelling	th-cmuir.6653943832-534162018-09-04T09:58:10Z The complexity of the overlay network verification and its related problems Wattana Jindaluang Sanpawat Kantabutra Varin Chouvatut Computer Science Mathematics Medicine © 2014 IEEE. In this paper we introduce a special type of virtual networks called an overlay network. We first study a decision problem called the OVERLAY NETWORK VERIFICATION PROBLEM and show that this problem is NP-complete. We then place some restriction to the original problem and prove that the OVERLAY NETWORK VERIFICATION PROBLEM still remains NP-complete. A similar problem called the TWO-LABEL OVERLAY NETWORK VERIFICATION PROBLEM is then investigated. The complexities of this problem and its variant are then discussed. A list of open problems and the real-world applications of our results are given in the conclusion. 2018-09-04T09:48:55Z 2018-09-04T09:48:55Z 2014-01-01 Conference Proceeding 2-s2.0-84942856816 10.1109/ICSEC.2014.6978123 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84942856816&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/53416
institution	Chiang Mai University
building	Chiang Mai University Library
country	Thailand
collection	CMU Intellectual Repository
topic	Computer Science Mathematics Medicine
spellingShingle	Computer Science Mathematics Medicine Wattana Jindaluang Sanpawat Kantabutra Varin Chouvatut The complexity of the overlay network verification and its related problems
description	© 2014 IEEE. In this paper we introduce a special type of virtual networks called an overlay network. We first study a decision problem called the OVERLAY NETWORK VERIFICATION PROBLEM and show that this problem is NP-complete. We then place some restriction to the original problem and prove that the OVERLAY NETWORK VERIFICATION PROBLEM still remains NP-complete. A similar problem called the TWO-LABEL OVERLAY NETWORK VERIFICATION PROBLEM is then investigated. The complexities of this problem and its variant are then discussed. A list of open problems and the real-world applications of our results are given in the conclusion.
format	Conference Proceeding
author	Wattana Jindaluang Sanpawat Kantabutra Varin Chouvatut
author_facet	Wattana Jindaluang Sanpawat Kantabutra Varin Chouvatut
author_sort	Wattana Jindaluang
title	The complexity of the overlay network verification and its related problems
title_short	The complexity of the overlay network verification and its related problems
title_full	The complexity of the overlay network verification and its related problems
title_fullStr	The complexity of the overlay network verification and its related problems
title_full_unstemmed	The complexity of the overlay network verification and its related problems
title_sort	complexity of the overlay network verification and its related problems
publishDate	2018
url	https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84942856816&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/53416
_version_	1681424131193569280

The complexity of the overlay network verification and its related problems

Similar Items