The Complexity of Problems on Graphs Represented as OBDDs
The Complexity of Problems on Graphs Represented as OBDDs
复制标题
以 OBDD 表示的图上问题的复杂性
DOI：
10.1007/bfb0028563
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Mahesh Viswanathan
中科院分区：
文献类型：
--
作者：
J. Feigenbaum;Sampath Kannan;Moshe Y. Vardi;Mahesh Viswanathan
为了分析图上决策问题的复杂性，通常假设输入大小是顶点数量的多项式。Galperin和Wigderson[13]以及后来的Papadimitriou和Yannakakis[13]研究了当输入图由多对数简洁电路表示时这些问题的复杂性。他们表明，在这样的表示下，某些琐碎的问题变得难以处理，而且，一般来说，问题的复杂性呈指数级增长。
To analyze the complexity of decision problems on graphs, one normally assumes that the input size is polynomial in the number of vertices. Galperin and Wigderson [13] and, later, Papadimitriou and Yannakakis [18] investigated the complexity of these problems when the input graph is represented by a polylogarithmically succinct circuit. They showed that, under such a representation, certain trivial problems become intractable and that, in general, there is an exponential blow up in problem complexity.