Chordal Graph, Perfect Elimination Ordering (MCS)
모든 4-cycle 이상이 chord 를 가지는 그래프. MCS (Maximum Cardinality Search) 로 정점을 뽑으며 각 단계에서 이웃들이 클리크를 이루면 PEO. max clique, chromatic, max independent set 모두 O(V+E) 에 해결.
메타데이터
| ID | chordal-graph |
| 카테고리 | algorithm |
| 버전 | v4 |
| 길이 | 13.0s (13000ms) |
| 구성 | 21 elements · 5 chapters · 6 effects |
| 태그 | #algorithm #graph #chordal-graph #perfect-elimination |
본문에 삽입
```anim:chordal-graph
{}
```