Finding good 2-partitions of digraphs. I. Hereditary properties

DOI10.1016/j.tcs.2016.05.029zbMath1342.68150OpenAlexW2284858747MaRDI QIDQ290530

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

Publication date: 1 June 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.029

zbMATH Keywords

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

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. II. Enumerable properties ⋮ Degree-constrained 2-partitions of graphs ⋮ Out-degree reducing partitions of digraphs ⋮ 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
• 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
• 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
• The dichromatic number of a digraph
• On the complexity of partitioning a graph into a few connected subgraphs
• Bipartition of graph under degree constraints
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Splitting digraphs
• A Min-Max Theorem on Tournaments
• 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. I. Hereditary properties