Some polynomial classes for the acyclic orientation with parity constraint problem
이 논문은 무순환 방향성 그래프에서 특정 정점 집합에 대한 홀수 차수 조건을 만족하는 방향성 할당 문제의 복잡성을 분석하고, 세 가지 필요 조건이 충분 조건이 되는 다항식 시간 해결 가능한 그래프 클래스들을 정의하며, 이러한 클래스 간의 포함 관계를 규명하고 직교곱 경로 및 사이클에 대한 해의 존재성을 특징짓는 구성적 알고리즘을 제시합니다.