Please use this identifier to cite or link to this item:
https://ruomoplus.lib.uom.gr/handle/8000/1906
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kaparis, Konstantinos | el |
dc.contributor.author | Letchford, Adam | el |
dc.contributor.author | Mourtos, Ioannis | el |
dc.date.accessioned | 2024-12-02T11:53:01Z | - |
dc.date.available | 2024-12-02T11:53:01Z | - |
dc.date.issued | 2023-11-01 | - |
dc.identifier.uri | https://ruomoplus.lib.uom.gr/handle/8000/1906 | - |
dc.description.abstract | The max-cut problem is a fundamental and much-studied NP-hard combinatorial optimisation problem, with a wide range of applications. Several authors have shown that the max-cut problem can be solved in polynomial time if the underlying graph is free of certain minors. We give a polyhedral counterpart of these results. In particular, we show that, if a family of valid inequalities for the cut polytope satisfies certain conditions, then there is an associated minor-closed family of graphs on which the max-cut problem can be solved efficiently. | el |
dc.language.iso | en | el |
dc.publisher | Elsevier | el |
dc.relation.ispartof | Discrete Optimization | el |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | FRASCATI__Social sciences__Economics and Business | el |
dc.subject.other | Combinatorial Optimisation | el |
dc.subject.other | Graph minor | el |
dc.subject.other | Max-cut | el |
dc.subject.other | Polyhedral Combinatorics | el |
dc.subject.other | Polytope | el |
dc.title | On cut polytopes and graph minors | el |
dc.type | journal article | el |
dc.identifier.doi | 10.1016/j.disopt.2023.100807 | - |
dc.identifier.scopus | 2-s2.0-85173627028 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/85173627028 | - |
dc.relation.issn | 1572-5286 | el |
dc.description.volume | 50 | el |
dc.description.startpage | 100807 | el |
dc.contributor.department | Department of Business Administration | el |
item.grantfulltext | embargo_20251101 | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.openairetype | journal article | - |
item.fulltext | With Fulltext | - |
item.languageiso639-1 | en | - |
item.cerifentitytype | Publications | - |
crisitem.journal.journalissn | 1572-5286 | - |
crisitem.author.dept | University of Macedonia | - |
crisitem.author.dept | University of Macedonia | - |
crisitem.author.department | Department of Business Administration | - |
crisitem.author.orcid | 0000-0002-5024-4674 | - |
crisitem.author.orcid | 0000-0002-3191-5006 | - |
crisitem.author.faculty | School of Business Administration | - |
Appears in Collections: | Articles |
Files in This Item:
File | Description | Size | Format | Existing users please |
---|---|---|---|---|
Cut_Polytopes_and_Graph_Minors.pdf | 400,89 kB | Adobe PDF | Request a copy | Embargoed until November 1, 2025
Page view(s)
34
checked on Feb 19, 2025
Download(s)
5
checked on Feb 19, 2025
Google ScholarTM
Check
Altmetric
Altmetric
This item is licensed under a Creative Commons License