Changes between Initial Version and Version 3 of Ticket #11736
 Timestamp:
 08/24/11 14:21:46 (9 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #11736

Property
Type
changed from
PLEASE CHANGE
toenhancement

Property
Type
changed from

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.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. 2 2 3 There is one thing, though: in [2]there is a new algorithm for is_interval() that avoids PQtrees, and just uses various passes of lex_BFS() (implemented with doubly linked lists).3 There is one thing, though: in (2) there is a new algorithm for is_interval() that avoids PQtrees, and just uses various passes of lex_BFS() (implemented with doubly linked lists). 4 4 So maybe in the long run it would be better to do it with doubly linked lists in Cython. 5 5 6 [1] Habib, McConnell, Paul and Viennot. LexBFS 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. LexBFS 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.