In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - LexBFS (fr)
- Lexicographic breadth-first search (en)
- Лексикографический поиск в ширину (ru)
- Лексикографічний пошук у ширину (uk)
|
| rdfs:comment
| - LexBFS, ou parcours en largeur lexicographique est un algorithme de théorie des graphes. C'est un raffinement de l'algorithme de parcours en largeur (BFS pour Breadth First Search en anglais). Ce parcours est très utile pour étudier certaines classes de graphes et pour obtenir des algorithmes de reconnaissance rapides de ces classes. (fr)
- Лексикографічний пошук у ширину (англ. lexicographic breadth-first search LBFS або Lex-BFS) — алгоритм упорядкування вершин графу. Алгоритм відрізняється від алгоритму пошуку в ширину і дає упорядкованішу[невідомий термін] послідовність вершин графу. Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав (2004). Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання хордальних графів, розфарбовування повністю розщеплюваних графів. (uk)
- In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search. (en)
- Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную[неизвестный термин] последовательность вершин графа. (ru)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| first
| - Robert E. (en)
- George S. (en)
- Donald J. (en)
|
| last
| - Rose (en)
- Lueker (en)
- Tarjan (en)
|
| year
| |
| has abstract
| - In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search. The lexicographic breadth-first search algorithm is based on the idea of partition refinement and was first developed by Donald J. Rose, Robert E. Tarjan, and George S. Lueker. A more detailed survey of the topic is presented by .It has been used as a subroutine in other graph algorithms including the recognition of chordal graphs, and optimal coloring of distance-hereditary graphs. (en)
- LexBFS, ou parcours en largeur lexicographique est un algorithme de théorie des graphes. C'est un raffinement de l'algorithme de parcours en largeur (BFS pour Breadth First Search en anglais). Ce parcours est très utile pour étudier certaines classes de graphes et pour obtenir des algorithmes de reconnaissance rapides de ces classes. (fr)
- Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную[неизвестный термин] последовательность вершин графа. Алгоритм лексикографического поиска в ширину основан на идее разбиения на подмножества и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004). Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание хордальных графов, раскраска полностью расщепляемых графов. (ru)
- Лексикографічний пошук у ширину (англ. lexicographic breadth-first search LBFS або Lex-BFS) — алгоритм упорядкування вершин графу. Алгоритм відрізняється від алгоритму пошуку в ширину і дає упорядкованішу[невідомий термін] послідовність вершин графу. Алгоритм лексикографічного пошуку в ширину ґрунтується на ідеї і вперше його розробили Роуз, Тарджан і Люкер (1976). Детальніший огляд теми надав (2004). Лексикографічний пошук у ширину використовується як частина в інших графічних алгоритмах, наприклад, розпізнавання хордальних графів, розфарбовування повністю розщеплюваних графів. (uk)
|
| author2-link
| |
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)