On semi-transitive orientability of split graphs Научная публикация
| Журнал |
Information Processing Letters
ISSN: 0020-0190 |
||||||
|---|---|---|---|---|---|---|---|
| Вых. Данные | Год: 2024, Том: 184, Номер статьи : 106435, Страниц : 4 DOI: 10.1016/j.ipl.2023.106435 | ||||||
| Ключевые слова | Semi-transitive orientation, Split graph, Polynomial solvability, Circular ones property, Computational complexity | ||||||
| Авторы |
|
||||||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
Реферат:
Adirected graph is semi-transitive if and only if it is acyclic and for any directed path u1 →u2 →···→ut, t ≥2, either there is no edge from u1 to ut or all edges ui → uj exist for 1 ≤ i < j ≤t. An undirected graph is semi-transitive if it admits a semi-transitive orientation. Recognizing semi-transitive orientability of a graph is an NP-complete problem. Asplit 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.
Библиографическая ссылка:
Kitaev S.
, Pyatkin A.
On semi-transitive orientability of split graphs
Information Processing Letters. 2024. V.184. 106435 :1-4. DOI: 10.1016/j.ipl.2023.106435 WOS Scopus РИНЦ OpenAlex
On semi-transitive orientability of split graphs
Information Processing Letters. 2024. V.184. 106435 :1-4. DOI: 10.1016/j.ipl.2023.106435 WOS Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 10 сент. 2022 г. |
| Принята к публикации: | 28 авг. 2023 г. |
| Опубликована online: | 1 сент. 2023 г. |
| Опубликована в печати: | 2 апр. 2024 г. |
Идентификаторы БД:
| Web of science: | WOS:001076813300001 |
| Scopus: | 2-s2.0-85170572963 |
| РИНЦ: | 64853990 |
| OpenAlex: | W4386374895 |