Learning a Bounded-Degree Tree Using Separator Queries
Learning a Bounded-Degree Tree Using Separator Queries
复制标题
使用分隔符查询学习有界度树
DOI：
10.1007/978-3-642-40935-6_14
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Anindya Sen
中科院分区：
文献类型：
--
作者：
M. Jagadish;Anindya Sen
假设有一棵无向树T，它包含n个结点，有界度d。我们知道T中的结点，但不知道边。问题是通过询问以下形式的查询来输出树T：“节点y是否位于节点x和节点z之间的路径上？”换句话说，我们可以问移除节点y是否会断开节点x与节点z的连接。这样的查询称为分隔符查询。假设每个查询都可以在恒定的时间内由一位先知回答。目标是根据n最小化输出树所花费的时间。
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.