Complexity of some arc-partition problems for digraphs
From MaRDI portal
Publication:2079880
DOI10.1016/j.tcs.2022.06.023OpenAlexW4282824801MaRDI QIDQ2079880
L. Picasarri-Arrieta, Daniel Gonçalves, 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
digraphspolynomial algorithmbranchingsNP-completeacyclic digraphcycle factorarc-partitionsstrong subdigraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding good 2-partitions of digraphs. I. Hereditary properties
- Decomposing locally semicomplete digraphs into strong spanning subdigraphs
- A short proof of the tree-packing theorem
- Arc-disjoint spanning sub(di)graphs in digraphs
- Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
- Bounded degree spanning trees (extended abstract)
- Edge-disjoint in- and out-branchings in tournaments and related path problems
- On two minimax theorems in graph
- Complexity of the hamiltonian cycle in regular graph problem
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- Parameterized complexity of Eulerian deletion problems
- Arc-disjoint paths and trees in 2-regular digraphs
- Finding good 2-partitions of digraphs. II. Enumerable properties
- On the Problem of Decomposing a Graph into n Connected Factors
- The circular chromatic number of a digraph
- Small degree out‐branchings
- Reducibility among Combinatorial Problems
- Digraphs
- Combinatorial optimization. Theory and algorithms
- Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
This page was built for publication: Complexity of some arc-partition problems for digraphs
