The complexity of SIMPLE MAX-CUT on comparability graphs

DOI10.1016/J.ENDM.2016.10.040zbMath1356.05093OpenAlexW2552930788MaRDI QIDQ510977

Rafael Veiga Pocai

Publication date: 14 February 2017

Full work available at URL: https://doi.org/10.1016/j.endm.2016.10.040

zbMATH Keywords

computational complexitycomparability graphsmax-cut

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Complexity-separating graph classes for vertex, edge and total colouring ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ Revising Johnson's table for the 21st century

Cites Work

• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• Crossing minimization in linear embeddings of graphs
• Unnamed Item

This page was built for publication: The complexity of SIMPLE MAX-CUT on comparability graphs