The complexity of SIMPLE MAX-CUT on comparability graphs

DOI10.1016/J.ENDM.2016.10.040MaRDI QIDQ510977zbMATH OpenOpenAlexFDO

Authors 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

comparability graphscomputational complexitymax-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)

Recommendations

• scientific article; zbMATH DE number 1496855
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• scientific article; zbMATH DE number 2044946
• SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
• scientific article; zbMATH DE number 780784

Cites work

• Crossing minimization in linear embeddings of graphs
• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)

Cited in

(6)

• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Revising Johnson's table for the 21st century
• Complexity-separating graph classes for vertex, edge and total colouring
• SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs

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

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