期刊
INFORMATION PROCESSING LETTERS
卷 184, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.ipl.2023.106435
关键词
Semi-transitive orientation; Split graph; Polynomial solvability; Circular ones property; Computational complexity
This article discusses the properties of semi-transitive directed graphs and split graphs, pointing out that recognizing the semi-transitive orientability is an NP-complete problem. It also proves that the recognition of semi-transitive orientability of split graphs can be done in polynomial time.
A directed graph is semi-transitive if and only if it is acyclic and for any directed path u(1)-> u(2)->& ctdot;-> u(t), t >= 2, either there is no edge from u1 to ut or all edges u(i)-> u(j) exist for 1 <= i<= t. Recognizing semi-transitive orientability of a graph is an NP-complete problem. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Semi-transitive orientability of split graphs was recently studied in a series of papers in the literature. The main result in this paper is proving that recognition of semi-transitive orientability of split graphs can be done in a polynomial time.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据