Access Restriction

Author Bergner, Martin ♦ Lbbecke, Marco E. ♦ Witt, Jonas T.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Column generation ♦ Branch-price-and-cut ♦ Packing problem
Abstract The cut packing problem in an undirected graph is to find a largest cardinality collection of pairwise edge-disjoint cuts. We provide the first experimental study of this NP-hard problem that is interesting from a pure theorist’s viewpoint as well as from the standpoint of scientific applications (e.g., in bioinformatics and network reliability). So far it could not be solved exactly. We propose a branch-price-and-cut algorithm to optimally solve instances from various graph classes, random and from the literature, with up to several hundred vertices. In particular, we investigate how complexity results match computational experience and how combinatorial properties help improve the algorithm’s performance.
Description Author Affiliation: RWTH Aachen University, Aachen, Germany (Bergner, Martin; Lbbecke, Marco E.; Witt, Jonas T.)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-01-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 16
Starting Page 1
Ending Page 16

Open content in new tab

   Open content in new tab
Source: ACM Digital Library