Finding good 2-partitions of digraphs. II. Enumerable properties

DOI10.1016/j.tcs.2016.05.034zbMath1345.68168OpenAlexW2283724883MaRDI QIDQ2629228

Nathann Cohen, Jörgen Bang-Jensen, Frédéric Havet

Publication date: 5 July 2016

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

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

zbMATH Keywords

partitionNP-completenesspolynomialtournamentminimum degreefeedback vertex setacyclic2-partitionout-branchingsemicomplete digraphsplitting digraphsoriented

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (8)

Finding good 2-partitions of digraphs. I. Hereditary properties ⋮ Degree-constrained 2-partitions of graphs ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ On the parameterized complexity of 2-partitions ⋮ Degree constrained 2-partitions of semicomplete digraphs ⋮ Complexity of some arc-partition problems for digraphs ⋮ The parameterized complexity landscape of finding 2-partitions of digraphs ⋮ Tournaments and Semicomplete Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Vertex-disjoint directed and undirected cycles in general digraphs
• On spanning galaxies in digraphs
• Arc-disjoint spanning sub(di)graphs in digraphs
• Finding a subdivision of a digraph
• Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz
• FPT algorithms for connected feedback vertex set
• Partition of graphs with condition on the connectivity and minimum degree
• A linear algorithm for bipartition of biconnected graphs
• Partitioning graphs into connected parts
• On the complexity of partitioning graphs into connected subgraphs
• Even cycles in directed graphs
• Partitions of graphs with high minimum degree or connectivity.
• Splitting a graph into disjoint induced paths or cycles.
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• On the complexity of partitioning a graph into a few connected subgraphs
• On the problem of finding disjoint cycles and dicycles in a digraph
• Bipartition of graph under degree constraints
• Defective coloring revisited
• Splitting digraphs
• Graph decomposition with constraints on the connectivity and minimum degree
• The circular chromatic number of a digraph
• The complexity of satisfiability problems
• Digraphs
• Connected Feedback Vertex Set in Planar Graphs

This page was built for publication: Finding good 2-partitions of digraphs. II. Enumerable properties