Degree constrained 2-partitions of semicomplete digraphs

DOI10.1016/J.TCS.2018.06.028zbMATH Open1401.05129OpenAlexW2809546411MaRDI QIDQ1784748FDOQ1784748

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

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

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)

Cites Work

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

Cited In (9)

• 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
• 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)