Paper Info
Title
Average running time analysis of an algorithm to calculate the size of the union of Cartesian products
Abstract
We consider the problem of calculating the size of the union of Cartesian products of finite sets of integers S"i"j, |@?"i"="1","...","nS"i"1x...xS"i"m|, where m denotes the dimension of the space and n the number of Cartesian products. This problem, denoted by SUCP, contains as a special case the problem of counting the number of satisfying assignments of the satisfiability problem (SAT). We present an algorithm to solve the problem SUCP, called the grouping method. For the average running time analysis, S"i"j are constructed by randomly selecting each element in set D={1,2,...,d} with probability p. We show that the average running time of the grouping method is O(mnd.min{(nd(1-p)+1)^m^-^1,d^m^-^1}), which is more efficient than the time complexity O(mnd^m) of the naive method if n(1-p)@?1 holds.
Year
DOI
Venue
2003
10.1016/S0012-365X(03)00239-5
Discrete Mathematics
Keywords
Field
DocType
cartesian product,average running time,satisfiability problem,time complexity,satisfiability,timing analysis
Integer,Discrete mathematics,Combinatorics,Finite set,Cartesian product,Boolean satisfiability problem,Algorithm,Time complexity,Mathematics,Special case
Journal
Volume
Issue
ISSN
273
1-3
Discrete Mathematics
Citations 
PageRank 
References 
0
0.34
4
Authors
2
Name
Order
Citations
PageRank
Susumu Suzuki100.34
Toshihide Ibaraki22593385.64