MaxCut on permutation graphs is NP‐complete

DOI10.1002/jgt.22948arXiv2202.13955MaRDI QIDQ6047965

Unnamed Author, Celina M. Herrera de Figueiredo, Fabiano S. Oliveira, Alexsander A. de Melo

Publication date: 10 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2202.13955

zbMATH Keywords

computational complexitymaximum cutNP-completepermutation graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Cites Work

• Interval graphs and interval orders
• Some simplified NP-complete graph problems
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• Revising Johnson's table for the 21st century
• The NP-completeness column: an ongoing guide
• Transitiv orientierbare Graphen
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Complexity of maximum cut on interval graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: MaxCut on permutation graphs is NP‐complete