Lexicographic breadth-first search (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:wikiPageExternalLink | https://archive.org/details/graphclassessurv0000bran http://www.liafa.jussieu.fr/~habib/Documents/cograph.ps%7Cciteseerx=10.1.1.188.5016 |
| dbo:wikiPageID | 22336498 (xsd:integer) |
| dbo:wikiPageLength | 11527 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116542984 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queue_(abstract_data_type) dbr:Depth-first_search dbr:Induced_subgraph dbc:Search_algorithms dbr:Graph_coloring dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Lexicographic_order dbr:Linear_time dbr:Comparability_graph dbr:Complement_graph dbr:Computer_science dbc:Graph_algorithms dbr:Adjacency_matrix dbr:Breadth-first_search dbr:Partition_refinement dbr:Graph_theory dbr:Interval_graph dbr:Chordal_graph dbr:Cograph dbr:Distance-hereditary_graph dbr:Sorting_algorithm dbr:Greedy_coloring dbr:Vertex_(graph_theory) dbr:Imperative_programming dbr:Pseudocode dbr:Lexicographical_order dbr:Queue_(data_structure) dbr:Partition_(set_theory) |
| dbp:author2Link | Robert Tarjan (en) |
| dbp:first | Robert E. (en) George S. (en) Donald J. (en) |
| dbp:last | Rose (en) Lueker (en) Tarjan (en) |
| dbp:wikiPageUsesTemplate | dbt:Graph_search_algorithm dbt:Citation dbt:Harvtxt dbt:Mvar dbt:Reflist dbt:Sfnp dbt:Harvs |
| dbp:year | 1976 (xsd:integer) |
| dct:subject | dbc:Search_algorithms dbc:Graph_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| 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) |
| rdfs:label | LexBFS (fr) Lexicographic breadth-first search (en) Лексикографический поиск в ширину (ru) Лексикографічний пошук у ширину (uk) |
| owl:sameAs | freebase:Lexicographic breadth-first search yago-res:Lexicographic breadth-first search wikidata:Lexicographic breadth-first search dbpedia-fr:Lexicographic breadth-first search dbpedia-hu:Lexicographic breadth-first search dbpedia-ru:Lexicographic breadth-first search dbpedia-sr:Lexicographic breadth-first search dbpedia-th:Lexicographic breadth-first search dbpedia-uk:Lexicographic breadth-first search https://global.dbpedia.org/id/4qDfF |
| prov:wasDerivedFrom | wikipedia-en:Lexicographic_breadth-first_search?oldid=1116542984&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Lexicographic_breadth-first_search |
| is dbo:wikiPageRedirects of | dbr:LexBFS dbr:Lexicographic_BFS |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Indifference_graph dbr:Trivially_perfect_graph dbr:Weak_ordering dbr:Breadth-first_search dbr:Partition_refinement dbr:Interval_graph dbr:Chordal_graph dbr:Perfectly_orderable_graph dbr:LexBFS dbr:Lexicographic_BFS |
| is foaf:primaryTopic of | wikipedia-en:Lexicographic_breadth-first_search |