#11736: Linear time implementation of lex_BFS()
----------------------------+-----------------------------------------------
Reporter: ddestrada | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.7.2
Component: graph theory | Keywords: lexbfs
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Description changed by ddestrada:
Old description:
> 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.
>
> 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).
> So maybe in the long run it would be better to do it with doubly linked
> lists in Cython.
>
> [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.
> [2] Corneil, Olariu and Stewart. The LBFS Structure and Recognition of
> Interval Graphs. SIAMDM 23(4), 2009.
New description:
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.
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).
So maybe in the long run it would be better to do it with doubly linked
lists in Cython.
(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.
(2) Corneil, Olariu and Stewart. The LBFS Structure and Recognition of
Interval Graphs. SIAMDM 23(4), 2009.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11736#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
