Complexity of some arc-partition problems for digraphs

DOI10.1016/J.TCS.2022.06.023MaRDI QIDQ2079880OpenAlexFDO

Authors Daniel Gonçalves, L. Picasarri-Arrieta, Jørgen Bang-Jensen, Stéphane Bessy

Publication date 7 October 2022

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

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

zbMATH Keywords

digraphsNP-completepolynomial algorithmacyclic digraphcycle factorbranchingsarc-partitionsstrong subdigraphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• Degree constrained 2-partitions of semicomplete digraphs
• The parameterized complexity landscape of finding 2-partitions of digraphs

Cites work

• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• scientific article; zbMATH DE number 50766 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A short proof of the tree-packing theorem
• Arc-disjoint paths and trees in 2-regular digraphs
• Arc-disjoint spanning sub(di)graphs in digraphs
• Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
• Bounded degree spanning trees (extended abstract)
• Combinatorial optimization. Theory and algorithms
• Complexity and approximability of extended spanning star forest problems in general and complete graphs
• Complexity of the hamiltonian cycle in regular graph problem
• Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
• Decomposing locally semicomplete digraphs into strong spanning subdigraphs
• Digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Network flows. Theory, algorithms, and applications.
• On the Problem of Decomposing a Graph into n Connected Factors
• On two minimax theorems in graph
• Parameterized complexity of Eulerian deletion problems
• Reducibility among combinatorial problems
• Small degree out‐branchings
• The circular chromatic number of a digraph

Cited in

(1)

• Complexity results on the decomposition of a digraph into directed linear forests and out-stars

This page was built for publication: Complexity of some arc-partition problems for digraphs

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