Bounded expansion (original) (raw)
In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs. (en) Кажуть, що сімейство графів має обме́жене розши́рення, якщо всі його мінори обмеженої глибини є розрідженими графами. Багато природних сімейств розріджених графів мають обмежене розширення. Близька, але сильніша властивість, поліноміа́льне розши́рення, еквівалентне існуванню теорем розбиття для цих сімейств. Сімейства з цими властивостями мають ефективні алгоритми для задач, у числі яких пошук ізоморфного підграфа і перевірка моделей для теорії першого порядку для графів. (uk) Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов. (ru) |
| dbo:wikiPageID | 47843724 (xsd:integer) |
| dbo:wikiPageLength | 9440 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1095408033 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queue_number dbr:Shallow_minor dbr:Degeneracy_(graph_theory) dbr:Algorithm dbc:Graph_minor_theory dbr:Robertson–Seymour_theorem dbr:1-planar_graph dbr:Genus dbr:Chromatic_number dbr:Clique_problem dbr:Graph_(discrete_mathematics) dbr:Model_checking dbr:Erdős–Rényi_model dbr:Linear_time dbr:Logic_of_graphs dbr:Planar_separator_theorem dbr:String_graph dbr:Euclidean_space dbr:Graph_theory dbr:Intersection_graph dbr:Biclique-free_graph dbr:Dominating_set dbr:Planar_graph dbr:Polynomial dbr:Polynomial-time_approximation_scheme dbr:Graph_invariant dbr:Dominating_set_problem dbr:Set_cover_problem dbr:Subgraph_isomorphism_problem dbr:Random_graph dbr:Book_thickness dbr:Maximum_independent_set_problem dbr:Sparse_graph |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_minor_theory |
| gold:hypernym | dbr:Graphs |
| rdfs:comment | In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs. (en) Кажуть, що сімейство графів має обме́жене розши́рення, якщо всі його мінори обмеженої глибини є розрідженими графами. Багато природних сімейств розріджених графів мають обмежене розширення. Близька, але сильніша властивість, поліноміа́льне розши́рення, еквівалентне існуванню теорем розбиття для цих сімейств. Сімейства з цими властивостями мають ефективні алгоритми для задач, у числі яких пошук ізоморфного підграфа і перевірка моделей для теорії першого порядку для графів. (uk) Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов. (ru) |
| rdfs:label | Bounded expansion (en) Ограниченное расширение графа (ru) Обмежене розширення графа (uk) |
| owl:sameAs | wikidata:Bounded expansion dbpedia-ru:Bounded expansion dbpedia-uk:Bounded expansion https://global.dbpedia.org/id/2NesY |
| prov:wasDerivedFrom | wikipedia-en:Bounded_expansion?oldid=1095408033&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Bounded_expansion |
| is dbo:wikiPageWikiLink of | dbr:Queue_number dbr:Shallow_minor dbr:Book_embedding dbr:Dense_graph dbr:Patrice_Ossona_de_Mendez dbr:1-planar_graph dbr:Glossary_of_graph_theory dbr:Model_checking dbr:Logic_of_graphs dbr:Planar_separator_theorem dbr:String_graph dbr:Grundy_number dbr:Subgraph_isomorphism_problem dbr:Twin-width |
| is foaf:primaryTopic of | wikipedia-en:Bounded_expansion |