Maximum directed cuts in graphs with degree constraints
type: Item
instance of: scholarly article
title: Maximum directed cuts in graphs with degree constraints
zbMATH Open document ID: 1256.05122
author: Xingxing Yu
author: Baogang Xu
published in: Graphs and Combinatorics
publication date: 2012-12-27T00:00:00Z
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 6118545
zbMATH Keywords: maximum directed cut
zbMATH Keywords: max cut problem
zbMATH Keywords: NP-hard problem
zbMATH Keywords: Hall ratio
zbMATH Keywords: acyclic digraph
zbMATH Keywords: digraphs containing no directed triangles
zbMATH Keywords: maximum dicut
zbMATH Keywords: directed cut
zbMATH Keywords: subcubic graph
zbMATH Keywords: triangle-free graph
MaRDI profile type: Publication
full work available at URL: s00373-011-1056-8
OpenAlex ID: W2066592985
cites work: Bipartite subgraphs
cites work: Maximum directed cuts in acyclic digraphs
cites work: Largest bipartite subgraphs in triangle-free graphs with maximum degree three
cites work: Hall ratio of the Mycielski graphs
cites work: Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs
cites work: Some Extremal Properties of Bipartite Subgraphs
cites work: Improved approximation of Max-Cut on graphs of bounded degree
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: MAX CUT in cubic graphs
cites work: Extremal bipartite subgraphs of cubic triangle-free graphs
cites work: Q4305534
cites work: Maximum directed cuts in digraphs with degree restriction
cites work: Q3898517
cites work: Triangle-free subcubic graphs with minimum bipartite density
cites work: Node-and edge-deletion NP-complete problems
DOI: 10.1007/S00373-011-1056-8
description: scientific article; zbMATH DE number 6118545