Degree constrained 2-partitions of semicomplete digraphs

DOI10.1016/J.TCS.2018.06.028MaRDI QIDQ1784748zbMATH OpenOpenAlexFDO

Authors 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

NP-completetournament2-partitionsemicomplete digraphminimum out-degreeminimum semi-degreedigraphs of bounded independence numberminimum in-degree

Mathematics Subject Classification ID

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

Recommendations

• Finding good 2-partitions of digraphs. I. Hereditary properties
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Bipartite spanning sub(di)graphs induced by 2-partitions
• Out-degree reducing partitions of digraphs
• Out-colourings of digraphs

Cites work

• scientific article; zbMATH DE number 3914352 (Why is no real title available?)
• scientific article; zbMATH DE number 475591 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• Digraphs
• Disjoint cycles in digraphs
• Disjoint directed cycles
• Finding complementary cycles in locally semicomplete digraphs
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Finding good 2-partitions of digraphs. II. Enumerable properties
• On complementary cycles in locally semicomplete digraphs
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• The complexity of satisfiability problems
• The partition of a strong tournament
• Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz

Cited in

(10)

• Bipartite spanning sub(di)graphs induced by 2-partitions
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Out-colourings of digraphs
• Classes of intersection digraphs with good algorithmic properties
• Tournaments and Semicomplete Digraphs
• Semicomplete Multipartite Digraphs
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Complexity of some arc-partition problems for digraphs
• On the parameterized complexity of 2-partitions
• The parameterized complexity landscape of finding 2-partitions of digraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1784748)