| 1. |
- Alstrup, S, et al.
(författare)
-
Dynamic nested brackets
- 2004
-
Ingår i: Information and Computation. - : Elsevier BV. - 1090-2651 .- 0890-5401. ; 193:2, s. 75-83
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of maintaining a string of n brackets '('or')' under the operation reverse(i) that changes the ith bracket from '('to')' or vice versa, and returns 'yes' if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(log n/log log n) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Omega(Iog n/log log n) per operation in the cell probe model. (C) 2004 Elsevier Inc. All rights reserved.
|
|
| 2. |
- Björklund, Andreas, et al.
(författare)
-
Approximating longest directed paths and cycles
- 2004
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349. ; 3142, s. 222-233
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on n vertices. We show that neither of these two problems can be polynomial time approximated within n(1-epsilon)for any epsilon > 0 unless P = NP. In particular, the result holds for digraphs of constant bounded outdegree that contain a Hamiltonian cycle. Assuming the stronger complexity conjecture that Satisfiability cannot be solved in subexponential time, we show that there is no polynomial time algorithm that finds a directed path of length Omega(f(n) log(2) n), or a directed cycle of length Omega(f(n) log n), for any nondecreasing, polynomial time computable function f in w(1). With a recent algorithm for undirected graphs by Gabow, this shows that long paths and cycles are harder to find in directed graphs than in undirected graphs. We also find a directed path of length Omega(log(2) n/log log n) in Hamiltonian digraphs with bounded outdegree. With our hardness results, this shows that long directed cycles are harder to find than a long directed paths. Furthermore, we present a simple polynomial time algorithm that finds paths of length Omega(n) in directed expanders of constant bounded outdegree.
|
|
| 3. |
- Björklund, Andreas, et al.
(författare)
-
Finding a path of superlogarithmic length
- 2003
-
Ingår i: SIAM Journal on Computing. - 0097-5397. ; 32:6, s. 1395-1402
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of finding a long, simple path in an undirected graph. We present a polynomial-time algorithm that finds a path of length Omega((log L/log log L)(2)), where L denotes the length of the longest simple path in the graph. This establishes the performance ratio O(n( log log n/log n)(2)) for the longest path problem, where n denotes the number of vertices in the graph.
|
|
| 4. |
- Björklund, Andreas, et al.
(författare)
-
Finding a path of superlogarithmic length
- 2002
-
Ingår i: Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings. - 3540438645 ; LNCS 2380, s. 985-992
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of nding a long, simple path in anundirected graph.W e present a polynomial-time algorithm that ndsa path of length (log L/ log log L)2, where L denotes the length ofthe longest simple path in the graph.This establishes the performanceratio O|V |(log log |V |/ log |V |)2 for the Longest Path problem, whereV denotes the graphs vertices.
|
|
| 5. |
- Gudmundsson, J, et al.
(författare)
-
Lower bounds for approximate polygon decomposition and minimum gap
- 2002
-
Ingår i: Information Processing Letters. - 0020-0190. ; 81:3, s. 137-141
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of decomposing polygons (with holes) into various types of simpler polygons. We focus on the problem of partitioning a rectilinear polygon, with holes, into rectangles, and show an Omega (n log n) lower bound on the time-complexity. The result holds for any decomposition, optimal or approximative. The bound matches the complexity of a number of algorithms in the literature, proving their optimality and settling the complexity of approximate polygon decomposition in these cases. As a related result we show that any non-trivial approximation algorithm for the minimum gap problem requires Omega (n log n) time. (C) 2002 Elsevier Science B.V. All rights reserved.
|
|
| 6. |
- Husfeldt, Thore, et al.
(författare)
-
New lower bound techniques for dynamic partial sums and related problems
- 2003
-
Ingår i: SIAM Journal on Computing. - 0097-5397. ; 32:3, s. 736-753
-
Tidskriftsartikel (refereegranskat)abstract
- We study the complexity of the dynamic partial sum problem in the cell-probe model. We give the model access to nondeterministic queries and prove that the problem remains hard. We give the model access to the right answer +/-1 as an oracle and prove that the problem remains hard. This suggests which kind of information is hard to maintain. From these results, we derive a number of lower bounds for dynamic algorithms and data structures: We prove lower bounds for dynamic algorithms for existential range queries, reachability in directed graphs, planarity testing, planar point location, incremental parsing, and fundamental data structure problems like maintaining the majority of the prefixes of a string of bits. We prove a lower bound for reachability in grid graphs in terms of the graph's width. We characterize the complexity of maintaining the value of any symmetric function on the prefixes of a bit string.
|
|
