Name
Abstract | ||
|---|---|---|
We consider the problem of evaluating an expression consisting of unions and intersections of some sorted sets. Given the expression and the sizes of the sets, we are interested in the worst-case complexity of evaluating the expression in terms of the sizes of the sets. We assume no set is repeated in the expression. We show a lower bound on this problem and present an algorithm that matches the lower bound asymptotically. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11523468_15 | ICALP |
Keywords | Field | DocType |
lower bound asymptotically,worst-case complexity,worst case optimal union-intersection,expression evaluation,lower bound | Discrete mathematics,Combinatorics,Upper and lower bounds,Automaton,Mathematics,Scalability | Conference |
Volume | ISSN | ISBN |
3580 | 0302-9743 | 3-540-27580-0 |
Citations | PageRank | References |
7 | 0.50 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehsan Chiniforooshan | 1 | 118 | 16.38 |
| Arash Farzan | 2 | 136 | 11.07 |
| Mehdi Mirzazadeh | 3 | 13 | 1.74 |