학술
기타
Finding forest-orderings of tournaments is NP-complete
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.Abstract
Given a class of (undirected) graphs $\mathcal{C}$, we say that a Feedback Arc Set (FAS for short) $F$ is a $\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their orientations) belongs to $\mathcal{C}$.
We show that deciding if a tournament has a $\mathcal{C}$-FAS is NP-complete when $\mathcal{C}$ is the class of all forests.
We are motivated by connections between $\mathcal{C}$-FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erdős-Hajnal property.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요
관련 뉴스
관련 뉴스 제보는 로그인 후 가능합니다.
'research' 카테고리 뉴스
The strip-shaped deep white matter hyperintensities may be related to neurodegeneration: A study based on diffusion tensor imaging
PLOS ONE
Data-driven analysis of heterogeneous gait subgroups and ground reaction forces based on integrated center of pressure–center of mass dynamics in poststroke hemiparesis
PLOS ONE
Correction: Study on plugging law and plugging removal effect of pre filled screen in natural gas hydrate argillaceous silt reservoir
PLOS ONE