2021-09-29T12:33:37Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001505762017-03-31T05:33:31Z08512:08654:08655:08540:08541
A-020 Efficient algorithms for network localization using cores of underlying graphsenghttp://id.nii.ac.jp/1001/00150542/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=150576&item_no=1&attribute_id=1&file_no=1Copyright (c) 2011 by IEICE,IPSJ東北大東北大東北大李, 甍大舘, 陽太徳山, 豪Network localization is important for networks with no prefixed positions of network nodes such as (sensor networks. We are given a subset of the set of (^n_2) pairwise distances among n sensors in some Euclidean space. We want to determine the positions of each sensors from the (partial) distance information. The input can be seen as an edge weighted graph. In this paper, we present some efficient algorithms that solve this problem using the structures of input graphs, which we call the cores of them. For instance, we present a polynomial-time algorithm solving the network localization problem for graphs with connected dominating sets of bounded size. This algorithm allows us to have an FPT algorithm for some restricted instances such as graphs with connected vertex covers of bounded size.AA1242354X情報科学技術フォーラム講演論文集1011911962011-09-072016-02-12