| dbo:abstract
|
- In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete. (en)
- У теорії графів цілком упорядковуваний граф — це граф, вершини якого можна впорядкувати так, що алгоритм жадібного розфарбовування з цим упорядкуванням оптимально розфарбовує будь-який породжений підграф даного графу. Відповідне впорядкування називається досконалим. Цілком упорядковувані графи утворюють підклас досконалих графів і в цей підклас входять хордальні графи, графи порівнянності і дистанційно-успадковувані графи. Однак перевірка, чи є граф цілком упорядковуваним, є NP-повною задачею. (uk)
- В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение называется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача. (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10268 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete. (en)
- У теорії графів цілком упорядковуваний граф — це граф, вершини якого можна впорядкувати так, що алгоритм жадібного розфарбовування з цим упорядкуванням оптимально розфарбовує будь-який породжений підграф даного графу. Відповідне впорядкування називається досконалим. Цілком упорядковувані графи утворюють підклас досконалих графів і в цей підклас входять хордальні графи, графи порівнянності і дистанційно-успадковувані графи. Однак перевірка, чи є граф цілком упорядковуваним, є NP-повною задачею. (uk)
- В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение называется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача. (ru)
|
| rdfs:label
|
- Perfectly orderable graph (en)
- Вполне упорядочиваемый граф (ru)
- Цілком упорядковуваний граф (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
