재귀적으로 가장 큰 첫 번째 알고리즘

RLF(Recursive Marge First) 알고리즘은 NP 하드그래프 컬러링 문제에 대한 휴리스틱입니다.그것은 1979년 ^[1]프랭크 레이튼에 의해 처음 제안되었다.

RLF 알고리즘은 각 색상 클래스를 한 번에 하나씩 구성하여 그래프의 정점에 색상을 할당합니다.그래프에서 최대 독립 정점 집합을 식별하고 동일한 색상에 할당한 다음 이러한 정점을 그래프에서 제거함으로써 이를 수행합니다.이러한 작업은 정점이 남아 있지 않을 때까지 나머지 하위 그래프에서 반복됩니다.

고품질 솔루션(몇 가지 색상을 사용한 솔루션)을 형성하기 위해 RLF 알고리즘은 특수 휴리스틱 규칙을 사용하여 "양질의" 독립 집합을 식별하려고 합니다.이러한 휴리스틱에 의해 RLF 알고리즘은 초당, 주기 및 휠 ^[2]그래프에 대해 정확해집니다.그러나 일반적으로 알고리즘은 근사치이며 그래프의 색수보다 더 많은 색상을 사용하는 솔루션을 반환할 수 있습니다.

묘사

알고리즘은 다음 3단계로 설명할 수 있습니다.이 프로세스의 마지막에 S$(\displaystyle {S})$는 $그래프{\displaystyle \mathcal{}}$$G{\displaystyle }$(\$displaystyle$ G$)$의 실현 ${\displaystyle 가능}$한 S$displaystyle {S}})$를 나타내는 정점 분할을 제공합니다.

1. $S$ ${\displaystyle =}$ $∅$ { style {S}$$= \$emptyset$ }을$($를) 빈 솔루션이라고 $합니다{\displaystyle \mathcal{}}$.Also, let ${\displaystyle G=(V,E)}$ be the graph we wish to color, comprising a vertex set ${\displaystyle V}$ and an edge set ${\displaystyle E}$.
2. 최대 독립 ${\displaystyle }$ S${\displaystyle v}$V(\$displaystyle$ S$\subseteq V$를 식별합니다.이 작업을 수행하려면 다음과 같이 하십시오.
   1. S ${\displaystyle$S}에 추가된 첫 번째 정점은$G$ {\$displaystyle$ G$}$에서 가장 많은 인접 관계를 가진 정점이 되어야 합니다.
   2. $S에 추가되는$$$후속 정점은 (a$)$$S의$ 정점에 현재 인접하지 않은 정점 및 ($b)$$S$의 정점에 인접하는 최대 수의 인접점을 가진 정점으로 선택해야 합니다. 조건 (b)의 동점은 최소 숫자의 정점을 선택함으로써 깨질 수 있습니다.S$${\$displaystyle$ S$\}$에 없는 인접 라우터의 ber. 정점은 S {\$displaystyle$ S$}$에 더 이상 정점을 추가할 수 없을 때까지 이 방법으로 추가됩니다.
3. 이제 ${\displaystyle S\mathcal{}}$ ${\displaystyle =}$ S${\displaystyle s}$ { S $}$ { $displaystyle {$S } { s } { $displaystyle$ { S$$} $= cup$\ { S$$ \ } } $s$ S의$$ 정점을$$G { $displaystyle$ G$$}에서 제거합니다. $그렇지{\displaystyle }$ 않으면$$G { $displaystyle$ G$$}에서$S$의 정점을 제거하고 2단계로 돌아갑니다.

예

오른쪽에 표시된 $그래프{\displaystyle }$ G $=$ ( ${\displaystyle V}$,${\displaystyle E}$) {$displaystyle$ G=($V,$E)}을$$ 참조하십시오.이 그래프는 휠 그래프이므로 RLF에 의해 최적으로 색상이 지정됩니다.알고리즘을 실행하면 다음 순서로 정점이 선택되고 색상이 지정됩니다.

1. $정점{\displaystyle }$ g$\$displaystyle g($표시 스타일$ g$)$
2. $꼭지점$a$,$ $c$ $,$ $displaystyle$ e$($컬러 2)
3. $정점{\displaystyle }$ b$($$색상$3) , $d{\displaystyle }$$,$ $f$$($$색상$ 3)

이로써 최종 3색 $솔루션{\displaystyle \mathcal{}}$ S ${\displaystyle =}${ { ${\displaystyle g}$ ${\displaystyle \}}$, {${\displaystyle a}$ ,${\displaystyle c}$ , ${\displaystyle e}$ ${\displaystyle \}}$, {${\displaystyle b}$ , ${\displaystyle d}$, ${\displaystyle f}$ $}$ { $displaystyle${$s }$= \ { \ { $a , c$ , e \ , \ } , \ { $b$, $d$, f \ }$$}가 됩니다.

성능

$n{\displaystyle }$ ${\displaystyle$ n$}$은 그래프의 꼭지점 수이고$$m {\$displaystyle$ m$}$은 모서리 수입니다.레이튼은 빅 O 표기법을 사용하여 원래 출판물에서 RLF의 복잡도를 O$($$n$3)로$$명시하고 있지만, 이를 개선할 수 있다$.$이 알고리즘의 비용의 대부분은 위에서 설명한 경험적 규칙에 따라 정점을 선택하는 2단계에 기인한다.실제로 독립 $집합{\displaystyle }$ S$(\displaystyle$ S$)$ 외에 정점이 선택될 때마다 채색되지 않은 각 정점에 대해 인접 관계에 대한 정보를 다시 계산해야 합니다.이러한 계산은 O${\displaystyle }$(${\displaystyle m}$) \ $displaystyle$\ $mathcal${$O$} $（$m ）${\displaystyle \mathrm{시간}}$으로 실행할 수 있습니다.즉, RLF의 전체 복잡도는${\displaystyle }O{\displaystyle \mathcal{}}$ ( ${\displaystyle m}$)$$\ $displaystyle$\ $mathcal$ {$O$ } （ m$）$ $。$^[2]

If the heuristics of Step 2 are replaced with random selection, then the complexity of this algorithm reduces to ${\displaystyle {\mathcal {O}}(n+m)}$; however, the resultant algorithm will usually return lower quality solutions compared to those of RLF.^[2]또한 초당, 주기 및 휠 그래프에 대해서도 정확하지 않습니다.

2021년 루이스의 경험적 비교에서 RLF는 $O{\displaystyle \mathcal{}}$${\displaystyle (}$${\displaystyle n}$+$)\style$ {$O$$}(n+$${\displaystyle m}$$)\$display style$($${\displaystyle n}$+ m${\displaystyle )}$ $lg$ $)\$displaystyle$(n$ + m)\$display$ style {O$}(n+m)\$lg$$ disperat discolat discolationsyle(n)과 같은 대체 휴리스틱스보다 훨씬 뛰어난 정점 컬러링을 생성하는 것으로 나타났다.그러나 RLF를 사용한 런타임은 전체 복잡성이 ^[2]높기 때문에 이러한 대안보다 더 높은 것으로 나타났다.

레퍼런스

외부 링크

• 고성능 그래프 착색 알고리즘 스위트 그래프 착색 알고리즘(C++에서 구현)은 그래프 착색 가이드: 알고리즘과 응용 프로그램(Springer International Publishers, 2021).