Degree constrained 2-partitions of semicomplete digraphs

DOI10.1016/J.TCS.2018.06.028zbMath1401.05129OpenAlexW2809546411MaRDI QIDQ1784748

Tilde My Christiansen, Jörgen Bang-Jensen

Publication date: 27 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.06.028

zbMATH Keywords

tournamentNP-complete2-partitionsemicomplete digraphminimum out-degreeminimum semi-degreedigraphs of bounded independence numberminimum in-degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Classes of intersection digraphs with good algorithmic properties ⋮ Tournaments and Semicomplete Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Disjoint cycles in digraphs
• Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz
• Disjoint directed cycles
• On complementary cycles in locally semicomplete digraphs
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Finding complementary cycles in locally semicomplete digraphs
• The partition of a strong tournament
• Finding good 2-partitions of digraphs. II. Enumerable properties
• The complexity of satisfiability problems
• Digraphs

This page was built for publication: Degree constrained 2-partitions of semicomplete digraphs