A branch-and-price-and-cut method for computing an optimal bramble

A branch-and-price-and-cut method for computing an optimal bramble

0.00 Avg rating0 Votes
Article ID: iaor201530302
Volume: 18
Issue: 11
Start Page Number: 168
End Page Number: 188
Publication Date: Nov 2015
Journal: Discrete Optimization
Authors: , ,
Keywords: graphs, heuristics
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 ) equ1 exists with node i equ2 belonging to one subgraph and node j equ3 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 equ4 has a treewidth of k 1 equ5. 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.

Reviews

Required fields are marked *. Your email address will not be published.