Maximum directed cuts in digraphs with degree restriction
From MaRDI portal
Publication:3633002
Abstract: For integers m,k >= 1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k.
Recommendations
- Maximum directed cuts in acyclic digraphs
- Maximum directed cuts in graphs with degree constraints
- Covering digraphs with small indegrees or outdegrees by directed cuts
- On maximum edge cuts of connected digraphs
- Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts
Cites work
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three
- MAX CUT in cubic graphs
- Maximum directed cuts in acyclic digraphs
- Node-and edge-deletion NP-complete problems
- On incidence coloring and star arboricity of graphs
- Triangle-free partial graphs and edge covering theorems
- Triangle-free subcubic graphs with minimum bipartite density
Cited in
(12)- A note on line digraphs and the directed max-cut problem
- On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees
- Oblivious algorithms for the maximum directed cut problem
- Covering digraphs with small indegrees or outdegrees by directed cuts
- Bounds on maximum weight directed cut
- Maximum directed cuts in graphs with degree constraints
- Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts
- Max Horn SAT and the minimum cut problem in directed hypergraphs
- On maximum edge cuts of connected digraphs
- Maximum directed cuts in acyclic digraphs
- Intersection properties of maximal directed cuts in digraphs
- Online Maximum Directed Cut
This page was built for publication: Maximum directed cuts in digraphs with degree restriction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3633002)
