Dynamic problem (algorithms)

<h2 id="special-cases">Special cases</h2>
<p>Incremental algorithms, or <a href="/facts/Online_algorithm/64TsU7Yz">online algorithms</a>, are algorithms in which only additions of elements are allowed, possibly starting from empty/trivial input data.
</p><p>Decremental algorithms are algorithms in which only deletions of elements are allowed, starting with the initialization of a full data structure.
</p><p>If both additions and deletions are allowed, the algorithm is sometimes called fully dynamic.
</p>
<h2 id="examples">Examples</h2>
<h3>Maximal element</h3>
<i>Static problem</i>
For a set of <i>N</i> numbers find the maximal one.
<p>The problem may be solved in O(<i>N</i>) time.
</p>
<i>Dynamic problem</i>
For an initial set of N numbers, dynamically maintain the maximal one when insertions and deletions are allowed.
<p>This is just the <i><a href="/facts/Priority_queue/1uXVo4Uf">priority queue</a> maintenance problem</i> allowing for insertions and deletions; it can be solved, for example, using a 
<a href="/facts/Binary_heap/YPJAEN94">binary heap</a> in 
  
    
      
        O
        (
        log
        ⁡
        N
        )
      
    
    {\displaystyle O(\log N)}
  
 time for an update and 
  
    
      
        O
        (
        1
        )
      
    
    {\displaystyle O(1)}
  
 time for a query, with 
  
    
      
        O
        (
        N
        )
      
    
    {\displaystyle O(N)}
  
 setup time (i.e., the initial processing of the data). Note that the value of <i>N</i> may change during the life of the structure.
</p>
<h3>Graphs</h3>
<p>Given a graph, maintain its parameters, such as connectivity, maximal degree, shortest paths, etc., when insertion and deletion of its edges are allowed.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p><p>Examples:
</p>
<ul><li>There is an algorithm that maintains the <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning forest</a> of a weighted, undirected graph, subject to edge deletions and insertions, in 
  
    
      
        O
        (
        
          n
          
            1
            
              /
            
            2
          
        
        )
      
    
    {\displaystyle O(n^{1/2})}
  
 time per update.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li>
<li>There is an algorithm that maintains the <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning forest</a> of a weighted, undirected graph, subject to edge deletions and insertions, in 
  
    
      
        O
        (
        
          n
          
            1
            
              /
            
            3
          
        
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(n^{1/3}\log n)}
  
 <a href="/facts/Amortized/9fFYenJz">amortized</a> time per update.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Dynamization/sdQ53h3z">Dynamization</a></li>
<li><a href="/facts/Dynamic_connectivity/L0DX80bl">Dynamic connectivity</a></li>
<li><a href="/facts/Kinetic_data_structure/410CqBg7">Kinetic data structure</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>D. Eppstein, Z. Galil, and G. F. Italiano.  "Dynamic graph algorithms". In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997. <a href="/wiki/D._Eppstein" target="_blank">/wiki/D._Eppstein</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Eppstein, David; Italiano, Giuseppe; Nissenzweig, Amnon (1997). "Sparsification—a technique for speeding up dynamic graph algorithms". Journal of the ACM. 44 (5): 669–696. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Henzinger, Monika; King, Valerie (2001). "Maintaining minimum spanning forests in dynamic graphs". SIAM Journal on Computing. 31 (2): 364–374. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Dynamic problem (algorithms) open-in-new

Dynamic problem (algorithms)