theory

그래프 종류

Tournament: 놀랍게도 항상 위상순서가 있다. 알고리즘 퍼즐에도 관련 문제 수록되어있음.

Chordal: http://www.secmem.org/blog/2019/03/10/Finding-perfect-elimination-ordering-in-choral-graphs/

Interval:

Planar: Counting perfect matchings in planar graphs https://people.maths.bris.ac.uk/~csxam/presentations/matchings.pdf https://en.wikipedia.org/wiki/FKT_algorithm

Graph의 Tree Decomposition과 TreeWidth

일반적 그래프의 Tree Decomposition은 NP거나 아무튼 어렵다는듯. 근데 특정 형태의 그래프들은 Tree Decompsition이 가능하고, 그때 묶이는 정점의 최대개수가 Tree는 1, 선인장은 2 등등 아무튼 tree width가 작은 그래프는 좋은 성질이 있다고 한다. 그게 뭐냐면 tree decomposition한 상태에서 트리의 각 정점그룹내 정점별로 bitmask(혹은 connection profile DP처럼 정점별로 다양한 상태를 가질수도 있긴 하지만 아무튼)로 상태를 표현해주면 그냥 Tree DP?DAG DP?가 되서 풀 수 있다고 한다.