Reconstruction and verification of chordal graphs with a distance oracle
Reconstruction and verification of chordal graphs with a distance oracle
复制标题
用距离预言机重建和验证弦图
DOI：
10.1016/j.tcs.2021.01.006
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Jianxin Wang
中科院分区：
文献类型：
--
作者：
Guozhen Rong;Wenjun Li;Yongjie Yang;Jianxin Wang
A hidden graph is a graph whose edge set is hidden. A distance oracle of a graph G is a black-box that receives two vertices of G and outputs the distance between the two vertices. Given a hidden graph, the reconstruction problem aims to identify the edges of the hidden graph by accessing a distance oracle, and the verification problem aims to check whether the hidden graph is equal to another given graph (not hidden). If the hidden graph G is a connected chordal graph, a Las Vegas reconstruction algorithm using O (Δ 3 2 Δ⋅ n (2 Δ+ log 2 n) log n) distance queries is known, where Δ is the maximum degree of G and n is the number of vertices of G. Improving upon this result, we present a reconstruction algorithm using only O (Δ 2 n log 2 n) distance queries. As a byproduct, we obtain a deterministic algorithm for the verification of chordal graphs with O (Δ 2 n log n) distance queries. Additionally, we derive a deterministic algorithm of reconstructing connected interval graphs using only O (Δ n) distance queries, and prove that reconstructing or verifying a connected interval graph needs Ω (Δ n) distance queries, which implies that this algorithm is the best possible in terms of the number of distance queries needed.
登录
查看更多内容
DOI：
10.4230/lipics.stacs.2016.5
发表时间：
2016-02
期刊：
--
影响因子：
--
作者：
Mikkel Abrahamsen;Gregory Bodwin;E. Rotenberg;Morten Stöckel
通讯作者：
Mikkel Abrahamsen;Gregory Bodwin;E. Rotenberg;Morten Stöckel
DOI：
--
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
Valerie King;Li Zhang;Yunhong Zhou
通讯作者：
Valerie King;Li Zhang;Yunhong Zhou
DOI：
10.1016/j.ipl.2006.08.013
发表时间：
2007-02
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
L. Reyzin;N. Srivastava
通讯作者：
L. Reyzin;N. Srivastava
DOI：
10.1109/sfcs.2002.1181943
发表时间：
2002-11
期刊：
The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
影响因子：
--
作者：
N. Alon;R. Beigel;S. Kasif;S. Rudich;B. Sudakov
通讯作者：
N. Alon;R. Beigel;S. Kasif;S. Rudich;B. Sudakov
DOI：
10.1007/11758471_10
发表时间：
2006-01-01
期刊：
ALGORITHMS AND COMPLEXITY, PROCEEDINGS
影响因子：
--
作者：
Erlebach, Thomas;Hall, Alexander;Mihalak, Matus
通讯作者：
Mihalak, Matus