Trapezoid graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Trapezoid graph''' --- трапециедальный граф. The ''' trapezoid graph''' is the intersection graph of a collection of trapezoids with corner po…») |
(нет различий)
|
Текущая версия от 17:05, 16 августа 2011
Trapezoid graph --- трапециедальный граф. The trapezoid graph is the intersection graph of a collection of trapezoids with corner points lying on two parallel lines. Note that trapezoid graphs are co-comparability graphs and hence they are perfect graphs. The coloring problems on trapezoid graphs, Hamiltonian cycle problem and others are solvable in a polynomial time.