| 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
| |
| dbo:wikiPageLength
|
- 9440 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
