Finding good 2-partitions of digraphs. I. Hereditary properties
Publication:290530
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
partitionNP-completenesspolynomialtournamentminimum degreefeedback vertex setacyclic2-partitionout-branchingsemicomplete digraphsplitting digraphs
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)
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