A branch-and-price-and-cut method for computing an optimal bramble
dc.contributor.author | Sonuç, Sibel Bilge | |
dc.contributor.author | Smith, J. C. | |
dc.contributor.author | Hicks, I. V. | |
dc.date.accessioned | 2016-06-29T13:04:23Z | |
dc.date.available | 2016-06-29T13:04:23Z | |
dc.date.issued | 2015 | |
dc.identifier.issn | 1873-636X | |
dc.identifier.uri | http://hdl.handle.net/10679/4057 | |
dc.identifier.uri | http://www.sciencedirect.com/science/article/pii/S1572528615000511 | |
dc.description | Due to copyright restrictions, the access to the full text of this article is only available via subscription. | |
dc.description.abstract | Given an undirected graph, a bramble is a set of connected subgraphs (called bramble elements) such that every pair of subgraphs either contains a common node, or such that an edge ( i , j ) exists with node i belonging to one subgraph and node j belonging to the other. In this paper we examine the problem of finding the bramble number of a graph, along with a set of bramble elements that yields this number. The bramble number is the largest cardinality of a minimum hitting set over all bramble elements on this graph. A graph with bramble number k has a treewidth of k - 1 . We provide a branch-and-price-and-cut method that generates columns corresponding to bramble elements, and rows corresponding to hitting sets. We then examine the computational efficacy of our algorithm on a randomly generated data set. | |
dc.description.sponsorship | Defense Threat Reduction Agency ; Air Force Office of Scientific Research ; Office of Naval Research | |
dc.language.iso | eng | en_US |
dc.publisher | Elsevier | |
dc.relation.ispartof | Discrete Optimization | |
dc.rights | restrictedAccess | |
dc.title | A branch-and-price-and-cut method for computing an optimal bramble | en_US |
dc.type | Article | en_US |
dc.peerreviewed | yes | |
dc.publicationstatus | published | en_US |
dc.contributor.department | Özyeğin University | |
dc.contributor.authorID | (ORCID 0000-0002-4003-9888 & YÖK ID ) Sonuç, Sibel | |
dc.contributor.ozuauthor | Sonuç, Sibel Bilge | |
dc.identifier.volume | 18 | |
dc.identifier.startpage | 168 | |
dc.identifier.endpage | 188 | |
dc.identifier.wos | WOS:000367484200009 | |
dc.identifier.doi | 10.1016/j.disopt.2015.09.005 | |
dc.subject.keywords | Bramble | |
dc.subject.keywords | Branch-and-price | |
dc.subject.keywords | Treewidth | |
dc.subject.keywords | Integer programming | |
dc.identifier.scopus | SCOPUS:2-s2.0-84946548467 | |
dc.contributor.authorFemale | 1 |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Share this page