검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs 대체 방향 그래프와 상호 비교 가능성 그래프의 교차점에 대한 참고 사항

Asahi TAKAOKA

  • 조회수

    0

  • 이것을 인용

요약 :

우리는 Ghouila-Houri의 정리와 유사한 진술이 상호 비교 가능성 그래프의 교대 방향에 대해 유지될 수 있는지 여부를 연구했습니다. 본 논문에서는 부정적인 대답을 제시한다. 우리는 상호 비교 가능성 그래프가 교대 및 비순환 방향을 갖는지 여부를 결정하는 것이 NP-완전임을 증명합니다. 따라서 비순환 교대 방향의 상호 비교 가능성 그래프는 교대 방향의 상호 비교 가능성 그래프의 적절한 하위 클래스를 형성합니다. 또한 분리 예, 즉 교대 방향이 비순환적이지 않도록 교대로 배향 가능한 상호 비교 가능성 그래프를 제공합니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1223-1227
발행일
2022/09/01
공개일
2022/03/07
온라인 ISSN
1745-1337
DOI
10.1587/transfun.2021DMP0001
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주
그래프와 네트워크, 알고리즘과 데이터 구조

작성자

Asahi TAKAOKA
  Muroran Institute of Technology

키워드