Complexity of some arc-partition problems for digraphs

DOI10.1016/J.TCS.2022.06.023OpenAlexW4282824801MaRDI QIDQ2079880FDOQ2079880

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

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)

Cites Work

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

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)