Standard

On semi-transitive orientability of split graphs. / Kitaev, Sergey; Pyatkin, Artem.

In: Information Processing Letters, Vol. 184, 106435, 02.2024.

Research output: Contribution to journal › Article › peer-review

Harvard

Kitaev, S & Pyatkin, A 2024, 'On semi-transitive orientability of split graphs', Information Processing Letters, vol. 184, 106435. https://doi.org/10.1016/j.ipl.2023.106435

APA

Kitaev, S., & Pyatkin, A. (2024). On semi-transitive orientability of split graphs. Information Processing Letters, 184, [106435]. https://doi.org/10.1016/j.ipl.2023.106435

Vancouver

Kitaev S, Pyatkin A. On semi-transitive orientability of split graphs. Information Processing Letters. 2024 Feb;184:106435. doi: 10.1016/j.ipl.2023.106435

Author

Kitaev, Sergey ; Pyatkin, Artem. / On semi-transitive orientability of split graphs. In: Information Processing Letters. 2024 ; Vol. 184.

BibTeX

@article{dc13ee7efe0540d89a5f9d0f8acf1c9c,
title = "On semi-transitive orientability of split graphs",
abstract = "A directed 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",
keywords = "Circular ones property, Computational complexity, Polynomial solvability, Semi-transitive orientation, Split graph",
author = "Sergey Kitaev and Artem Pyatkin",
note = "The work of the second author was partially supported by the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019 ). The authors are grateful to the unknown referee for helpful comments.",
year = "2024",
month = feb,
doi = "10.1016/j.ipl.2023.106435",
language = "English",
volume = "184",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On semi-transitive orientability of split graphs

AU - Kitaev, Sergey

AU - Pyatkin, Artem

N1 - The work of the second author was partially supported by the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019 ). The authors are grateful to the unknown referee for helpful comments.

PY - 2024/2

Y1 - 2024/2

N2 - A directed 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

AB - A directed 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

KW - Circular ones property

KW - Computational complexity

KW - Polynomial solvability

KW - Semi-transitive orientation

KW - Split graph

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85170572963&origin=inward&txGid=745d02cf8b4338c92a15027409ae6261

UR - https://www.mendeley.com/catalogue/a9be81f4-e8d0-3b8e-9cd8-848d3d870abf/

U2 - 10.1016/j.ipl.2023.106435

DO - 10.1016/j.ipl.2023.106435

M3 - Article

VL - 184

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 106435

ER -

ID: 59306434