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.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Perfectly orderable graph (en)
- Вполне упорядочиваемый граф (ru)
- Цілком упорядковуваний граф (uk)
|
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)
|
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
| |
has 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)
|
gold:hypernym
| |
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is foaf:primaryTopic
of | |