\textsc{max-cut} and containment relations in graphs

DOI10.1016/J.TCS.2012.02.036MaRDI QIDQ441861zbMATH OpenOpenAlexFDO

Authors Marcin Kamiński

Publication date 8 August 2012

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

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

zbMATH Keywords

\textsc{max-cut}induced subgraphminorsubgraph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Max-Cut and containment relations in graphs
• Max-cut in circulant graphs
• MaxCut in ${\bm H)$-Free Graphs
• Max-cut under graph constraints
• Maximum cuts in \(\mathscr{H} \)-free graphs
• On the maximum cardinality cut problem in proper interval graphs and related graph classes
• On maximum edge cuts of connected digraphs
• Combinatorial properties and the complexity of a max-cut approximation
• scientific article; zbMATH DE number 747030
• Node and edge relaxations of the max-cut problem

Cites work

• A characterization of weakly bipartite graphs
• A characterization of weakly bipartite graphs
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• A polynomial characterization of some graph partitioning problems
• A short proof of Guenin's characterization of weakly bipartite graphs
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Boundary classes of graphs for the dominating set problem
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• scientific article; zbMATH DE number 1187139 (Why is no real title available?)
• scientific article; zbMATH DE number 3641501 (Why is no real title available?)
• scientific article; zbMATH DE number 475621 (Why is no real title available?)
• scientific article; zbMATH DE number 1947048 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• scientific article; zbMATH DE number 1414279 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• Max-Cut and containment relations in graphs
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Maximum cut on line and total graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Node-and edge-deletion NP-complete problems
• NP-hard graph problems and boundary classes of graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Optimization via enumeration: A new algorithm for the max cut problem
• Quickly excluding a forest
• Reducibility among combinatorial problems
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Weakly bipartite graphs and the max-cut problem

Cited in

(17)

• Seminormality, canonical modules, and regularity of cut polytopes
• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Approximating max-cut under graph-MSO constraints
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Boundary classes for graph problems involving non-local properties
• Max-Cut and containment relations in graphs
• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Complexity of maximum cut on interval graphs
• Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
• Complexity framework for forbidden subgraphs. IV: The Steiner forest problem
• On cut polytopes and graph minors
• Complexity framework for forbidden subgraphs. IV: The Steiner forest problem
• Complexity framework for forbidden subgraphs. I: The framework
• Graph homomorphism, monotone classes and bounded pathwidth
• Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs
• An overview of universal obstructions for graph parameters
• Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\)

This page was built for publication: \textsc{max-cut} and containment relations in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441861)