Canonical cuts of path powers

DOI10.55016/ojs/cdm.v19i3.72392MaRDI QIDQ6641096

Marisa Gutierrez, Mathieu Dutour Sikirić, Rubens A. Sucupira, Uéverton S. Souza, Luérbio Faria, Sulamita Klein, Celina M. Herrera de Figueiredo, Liliana Alcón

Publication date: 20 November 2024

Published in: Contributions to Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chain graphsunit interval graphsmaxcutpower of paths

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
• The max-cut problem on graphs not contractible to \(K_ 5\)
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Max-cut in circulant graphs
• Some simplified NP-complete graph problems
• Maximum cut on line and total graphs
• The maximum cardinality cut problem in co-bipartite chain graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Canonical cuts of path powers