Changes between Initial Version and Version 3 of Ticket #11736


Ignore:
Timestamp:
08/24/11 14:21:46 (8 years ago)
Author:
ddestrada
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #11736

    • Property Type changed from PLEASE CHANGE to enhancement
  • Ticket #11736 – Description

    initial v3  
    1 The current implementation of lex_BFS() is quadratic, which is not optimal. The usual way to do it in linear time is through a clever use of doubly linked lists, but in [1] there is a way with static arrays, which I coded in Python.
     1The current implementation of lex_BFS() is quadratic, which is not optimal. The usual way to do it in linear time is through a clever use of doubly linked lists, but in (1) there is a way with static arrays, which I coded in Python.
    22
    3 There is one thing, though: in [2] there is a new algorithm for is_interval() that avoids PQ-trees, and just uses various passes of lex_BFS() (implemented with doubly linked lists).
     3There is one thing, though: in (2) there is a new algorithm for is_interval() that avoids PQ-trees, and just uses various passes of lex_BFS() (implemented with doubly linked lists).
    44So maybe in the long run it would be better to do it with doubly linked lists in Cython.
    55
    6 [1] Habib, McConnell, Paul and Viennot. Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing. TCS 234, 2000.
    7 [2] Corneil, Olariu and Stewart. The LBFS Structure and Recognition of Interval Graphs. SIAMDM 23(4), 2009.
     6(1) Habib, McConnell, Paul and Viennot. Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing. TCS 234, 2000.
     7
     8(2) Corneil, Olariu and Stewart. The LBFS Structure and Recognition of Interval Graphs. SIAMDM 23(4), 2009.