Jump to content

Talk:Lexicographic breadth-first search

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
The algorithm is called lexicographic breadth-first search because the lexicographic order it produces is an ordering that could also have been produced by a breadth-first search, and because if the ordering is used to index the rows and columns of an adjacency matrix of a graph then the algorithm sorts the rows and columns into Lexicographical order.

I believe that part of this sentence is wrong. It is correct that LexBFS produces a BFS ordering. However, it is incorrect that it "sorts the rows and columns into Lexicographical order". Explicit and simple counter-examples exist. The problem is that this would imply that the nodes are selected by order of decreasing label. This is not true. --86.219.206.136 (talk) 09:45, 24 December 2011 (UTC)Charles Bouillaguet (charles.bouillaguet@gmail.com)[reply]

Who said anything about rows and columns? It sorts the vertices into lexicographic order by their sorted sequences of neighbors. —David Eppstein (talk) 16:56, 24 December 2011 (UTC)[reply]
The paragraph in question clearly mentions rows and columns. What is more important: LexBFS "as is" only sorts the vertices according to there earlier neighbors (in the sort order) and it does not produce columns/rows in lexicographical order (try e.g. a K_3 with an additional vertex attached to one of its vertices and start the search from a non-neighbor of the additional vertex). If you choose vertices with maximal degrees (and put ones on the main diagonal) this works, however this is unnecessary for most applications and thus not part of the usual algorithm and should not be stated as its property. My edit (which you reverted with the misleading comment "[...] loses the explanatiion for the lexicographic part") explained this explicitly. Frafl (talk) 21:50, 23 June 2015 (UTC)[reply]


I find the pseudo-code of the chordal graphs application a bit confusing. Assuming the LexBFS algorithm results in the order v_1...v_n, the perfect elimination would be the reversed sequence v_n...v_1. I will call this latter sequence Q. In this sequence, all neighbors v_x of v_i for which x < i (they occur later in the perfect elimination sequence) form a clique. Now the algorithm states the following:

  • Use lexicographic breadth-first search to find a lexicographic ordering of G
  • Reverse this ordering → this leads to the sequence Q
  • For each vertex v = v_i:
    • Let w = v_j be the neighbor of v occurring prior to v in the reversed sequence, as close to v in the sequence as possible → I take it that 'the reversed sequence' refers to sequence Q, thus we have something of the form v_n...w...v...v_1
      • (Continue to the next vertex v if there is no such w)
    • If the set of earlier neighbors of v (excluding w itself) is not a subset of the set of earlier neighbors of w, the graph is not chordal → if "the earlier neighbors of" refer to the sequence Q (meaning a node v_x is earlier than the node v_y <=> x > y), then the algorithm does not make any sense (a perfect elimination ordering is about neighbors occurring later in that order). However, if it refers to the original sequence v_1...v_n (meaning a node v_x is considered earlier than the node v_y <=> x < y), then the set of earlier nodes of w (excluding v itself) has to be a subset of the earlier neighbors of v and not the other way around because if w has a neighbor v_x with x < i that is not a neighbor of v, the earlier neighbors of w do not form a clique.
  • If the loop terminates without showing that the graph is not chordal, then it is chordal.

Of course, if the roles of v and w are swapped, there is no error. Therefore, I think the sentence «Let w be the neighbor of v occurring prior to v in the reversed sequence, as close to v in the sequence as possible» should be clarified so that the result is of the form v_n...v...w...v_1, in particular I would name the sequences and refer to them by their names so that no ambiguity is introduced.

Robbeblock (talk) 14:04, 20 May 2014 (UTC)[reply]

Ok, please do clean this up. There's an implemenation of this algorithm that you may find it helpful to refer to, at http://www.ics.uci.edu/~eppstein/PADS/Chordal.py — it differs from what's described here in that it doesn't reverse the LexBFS sequence until it is done checking the neighborhoods. —David Eppstein (talk) 15:53, 20 May 2014 (UTC)[reply]

goddisignz 09:04, 27. Aug 2015 (CEST)

I implemented the lexicographic breadth first search and assumed that if w is an earlier neighbor of v in the reverse sequence (Q), the index of w in Q is smaller than the index of v in Q. Then it only gave the correct result when I did NOT reverse the sequence. Maybe someone should clarify what "prior" really means. — Preceding unsigned comment added by Goddisignz (talk • contribs) 07:06, 27 August 2015 (UTC)[reply]
[edit]

Hello fellow Wikipedians,

I have just modified one external link on Lexicographic breadth-first search. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 08:14, 22 December 2017 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Lexicographic_breadth-first_search&oldid=1203576818"