랭크 폭
Rank-width |
랭크 폭은 그래프 이론 및 파라미터화된 복잡도에서 사용되는 그래프 폭 파라미터입니다.이 파라미터는 각 절단이 최대 k개의 순위 행렬을 유도하도록 정점을 분할하여 트리를 트리 같은 구조로 분해할 수 있도록 주어진 그래프 G에 대한 최소 정수 k를 나타냅니다.매우 유용한 다른 다양한 폭 파라미터가 있지만 트리 폭(또는 clique-width)과 같은 일부 파라미터는 스파스(또는 고밀도) 그래프에만 한정됩니다.clique-width를 사용할 수 있는 고밀도 그래프의 경우 이 파라미터를 결정하는 효율적인 알고리즘은 없습니다.바로 이 점이 중요한 부분이다.입력 그래프의 순위 폭이 최대 k인지 아닌지를 결정하는 알고리즘이 다항 시간에 실행됩니다.
랭크 폭과 clique 폭 사이의 가장 잘 알려진 관계는 다음과 같습니다. c k + - \ k \ 2 ^ { + 。여기서 c는 clique 폭입니다.
