Completing orientations of partially oriented graphs

DOI10.1002/jgt.22157zbMath1386.05121arXiv1509.01301OpenAlexW2963127852MaRDI QIDQ4638628

Xuding Zhu, Jing Huang, Jörgen Bang-Jensen

Publication date: 27 April 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.01301

zbMATH Keywords

polynomial time algorithmNP-completenessrecognitionin-tournamentproper interval graphlocal tournamentproper circular arc graphrepresentation extensionfriendly partial oriented graphlocally transitive local tournamentorientation completion problempartially oriented graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (9)

Extending partial representations of interval graphs ⋮ The complexity of 2-vertex-connected orientation in mixed graphs ⋮ Coloring mixed and directional interval graphs ⋮ Enumerating \(k\)-arc-connected orientations ⋮ Minimal obstructions for partial representations of interval graphs ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Extending partial representations of proper and unit interval graphs ⋮ Lexicographic Orientation Algorithms ⋮ Obstructions for acyclic local tournament orientation completions

This page was built for publication: Completing orientations of partially oriented graphs