Author
Sonuç, Sibel Bilge, Smith, J. C., Hicks, I. V.
Publication Date
2015
Publication Place
-
Elsevier
Subject
Bramble, Branch-and-price, Treewidth, Integer programming
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
1873-636X
Record ID
b890101e-2adf-41df-acc7-5f1e7a33d54d
Library Location
Industrial Engineering
Date
2015
Notes
Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Sample Text
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.
DOI
10.1016/j.disopt.2015.09.005
Cilt
18
