Please use this identifier to cite or link to this item: https://ruomoplus.lib.uom.gr/handle/8000/1906
DC FieldValueLanguage
dc.contributor.authorKaparis, Konstantinosel
dc.contributor.authorLetchford, Adamel
dc.contributor.authorMourtos, Ioannisel
dc.date.accessioned2024-12-02T11:53:01Z-
dc.date.available2024-12-02T11:53:01Z-
dc.date.issued2023-11-01-
dc.identifier.urihttps://ruomoplus.lib.uom.gr/handle/8000/1906-
dc.description.abstractThe 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.isoenel
dc.publisherElsevierel
dc.relation.ispartofDiscrete Optimizationel
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Διεθνές*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectFRASCATI__Social sciences__Economics and Businessel
dc.subject.otherCombinatorial Optimisationel
dc.subject.otherGraph minorel
dc.subject.otherMax-cutel
dc.subject.otherPolyhedral Combinatoricsel
dc.subject.otherPolytopeel
dc.titleOn cut polytopes and graph minorsel
dc.typejournal articleel
dc.identifier.doi10.1016/j.disopt.2023.100807-
dc.identifier.scopus2-s2.0-85173627028-
dc.identifier.urlhttps://api.elsevier.com/content/abstract/scopus_id/85173627028-
dc.relation.issn1572-5286el
dc.description.volume50el
dc.description.startpage100807el
dc.contributor.departmentDepartment of Business Administrationel
item.grantfulltextembargo_20251101-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
item.openairetypejournal article-
item.fulltextWith Fulltext-
item.languageiso639-1en-
item.cerifentitytypePublications-
crisitem.journal.journalissn1572-5286-
crisitem.author.deptUniversity of Macedonia-
crisitem.author.deptUniversity of Macedonia-
crisitem.author.departmentDepartment of Business Administration-
crisitem.author.orcid0000-0002-5024-4674-
crisitem.author.orcid0000-0002-3191-5006-
crisitem.author.facultySchool of Business Administration-
Appears in Collections:Articles
Files in This Item:
File Description SizeFormat Existing users please
Cut_Polytopes_and_Graph_Minors.pdf400,89 kBAdobe PDF
Embargoed until November 1, 2025    Request a copy
Show simple item record

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 Creative Commons