349:
29:
129:
Given a class of input objects, find efficient algorithms and data structures to answer a certain query about a set of input objects each time the input data is modified, i.e., objects are inserted or deleted.
271:
It is a simplified version of this dynamic problem, where one requires to delete only the maximal element. This version may do with simpler data structures.
280:
Given a graph, maintain its parameters, such as connectivity, maximal degree, shortest paths, etc., when insertion and deletion of its edges are allowed.
39:
409:
390:
141:
97:
125:
are problems stated in terms of changing input data. In its most general form, a problem in this category is usually stated as follows:
69:
258:. It takes space O(N), may be initially constructed in time O(N log N) and provides insertion, deletion and query times in O(log N).
255:
76:
414:
122:
54:
83:
211:
are algorithms in which only deletions of elements are allowed, starting with the initialization of a full data structure.
65:
383:
205:, are algorithms in which only additions of elements are allowed, possibly starting from empty/trivial input data.
250:
For an initial set of N numbers, dynamically maintain the maximal one when insertion and deletions are allowed.
156: – time required for the update of the data structure when one more input element is added;
376:
299:
90:
162: – time required for the update of the data structure when an input element is deleted;
326:
294:
17:
46:
360:
356:
202:
264:
403:
150: – time required for the initial construction of the data structure;
289:
318:
28:
214:
If both additions and deletions are allowed, the algorithm is sometimes called
348:
322:
182:
Many algorithmic problems stated in terms of fixed input data (called
175:
The overall set of computations for a dynamic problem is called a
133:
Problems in this class have the following measures of complexity:
22:
364:
50:
331:
CRC Handbook of
Algorithms and Theory of Computation
171:
Other operations specific to the problem in question
168: – time required to answer a query;
254:A well-known solution for this problem is using a
384:
8:
237:For a set of N numbers find the maximal one.
55:introducing citations to additional sources
391:
377:
241:The problem may be solved in O(N) time.
45:Relevant discussion may be found on the
311:
144:required to store the data structure;
7:
345:
343:
190:) have meaningful dynamic versions.
363:. You can help Knowledge (XXG) by
329:. "Dynamic graph algorithms". In
14:
256:self-balancing binary search tree
140: – the amount of
66:"Dynamic problem" algorithms
347:
38:relies largely or entirely on a
27:
410:Computational complexity theory
123:computational complexity theory
333:, Chapter 22. CRC Press, 1997.
186:in this context and solved by
1:
431:
342:
15:
16:Not to be confused with
415:Computer science stubs
300:Kinetic data structure
209:Decremental algorithms
199:Incremental algorithms
295:Dynamic connectivity
51:improve this article
267:maintenance problem
148:Initialization time
18:Dynamic programming
372:
371:
203:online algorithms
188:static algorithms
177:dynamic algorithm
116:
115:
101:
422:
393:
386:
379:
357:computer science
351:
344:
334:
316:
119:Dynamic problems
111:
108:
102:
100:
59:
31:
23:
430:
429:
425:
424:
423:
421:
420:
419:
400:
399:
398:
397:
340:
338:
337:
317:
313:
308:
286:
278:
246:Dynamic problem
229:
227:Maximal element
224:
196:
184:static problems
112:
106:
103:
60:
58:
44:
32:
21:
12:
11:
5:
428:
426:
418:
417:
412:
402:
401:
396:
395:
388:
381:
373:
370:
369:
352:
336:
335:
327:G. F. Italiano
310:
309:
307:
304:
303:
302:
297:
292:
285:
282:
277:
274:
273:
272:
269:
265:priority queue
252:
251:
248:
239:
238:
235:
233:Static problem
228:
225:
223:
220:
195:
192:
173:
172:
169:
163:
157:
154:Insertion time
151:
145:
131:
130:
114:
113:
49:. Please help
35:
33:
26:
13:
10:
9:
6:
4:
3:
2:
427:
416:
413:
411:
408:
407:
405:
394:
389:
387:
382:
380:
375:
374:
368:
366:
362:
359:article is a
358:
353:
350:
346:
341:
332:
328:
324:
320:
315:
312:
305:
301:
298:
296:
293:
291:
288:
287:
283:
281:
275:
270:
268:
266:
261:
260:
259:
257:
249:
247:
244:
243:
242:
236:
234:
231:
230:
226:
221:
219:
217:
216:fully dynamic
212:
210:
206:
204:
200:
194:Special cases
193:
191:
189:
185:
180:
178:
170:
167:
164:
161:
160:Deletion time
158:
155:
152:
149:
146:
143:
139:
136:
135:
134:
128:
127:
126:
124:
120:
110:
99:
96:
92:
89:
85:
82:
78:
75:
71:
68: –
67:
63:
62:Find sources:
56:
52:
48:
42:
41:
40:single source
36:This article
34:
30:
25:
24:
19:
365:expanding it
354:
339:
330:
314:
290:Dynamization
279:
262:
253:
245:
240:
232:
215:
213:
208:
207:
198:
197:
187:
183:
181:
176:
174:
165:
159:
153:
147:
142:memory space
137:
132:
118:
117:
104:
94:
87:
80:
73:
61:
37:
319:D. Eppstein
404:Categories
306:References
166:Query time
107:April 2024
77:newspapers
47:talk page
323:Z. Galil
284:See also
222:Examples
91:scholar
325:, and
276:Graphs
93:
86:
79:
72:
64:
355:This
201:, or
138:Space
98:JSTOR
84:books
361:stub
263:The
70:news
121:in
53:by
406::
321:,
218:.
179:.
392:e
385:t
378:v
367:.
109:)
105:(
95:·
88:·
81:·
74:·
57:.
43:.
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
