Learning a Bounded-Degree Tree Using Separator Queries
Abstract
Suppose there is an undirected tree T containing n nodes and having bounded degree d . We know the nodes in T but not the edges. The problem is to output the tree T by asking queries of the form: “Does the node y lie on the path between node x and node z ?”. In other words, we can ask if removing node y disconnects node x from node z . Such a query is called a separator query . Assume that each query can be answered in constant time by an oracle. The objective is to minimize the time taken to output the tree in terms of n . Our main result is an O ( dn ^1.5log n ) time algorithm for the above problem. To the best of our knowledge, no o ( n ^2) algorithm is known even for constant-degree trees. We also give an O ( d ^2 n log^2 n ) randomized algorithm and prove an Ω( dn ) lower bound for the same problem. Time complexity equals query complexity for all our results.
Cite
Text
Jagadish and Sen. "Learning a Bounded-Degree Tree Using Separator Queries." International Conference on Algorithmic Learning Theory, 2013. doi:10.1007/978-3-642-40935-6_14Markdown
[Jagadish and Sen. "Learning a Bounded-Degree Tree Using Separator Queries." International Conference on Algorithmic Learning Theory, 2013.](https://mlanthology.org/alt/2013/jagadish2013alt-learning/) doi:10.1007/978-3-642-40935-6_14BibTeX
@inproceedings{jagadish2013alt-learning,
title = {{Learning a Bounded-Degree Tree Using Separator Queries}},
author = {Jagadish, M. and Sen, Anindya},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2013},
pages = {188-202},
doi = {10.1007/978-3-642-40935-6_14},
url = {https://mlanthology.org/alt/2013/jagadish2013alt-learning/}
}