A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs

Autor:	Marco E. Lübbecke, Jonas Witt, Martin Bergner
Rok vydání:	2014
Předmět:	Discrete mathematics Combinatorics Packing problems Comparability graph Level structure Graph (abstract data type) Pairwise comparison Undirected graph Algorithm MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Experimental Algorithms ISBN: 9783319079585 SEA
DOI:	10.1007/978-3-319-07959-2_4
Popis:	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 interested theorists and practitioners alike. 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 improving the algorithm's performance.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6cdc695e4dacf7b68b9b33a362e94c67 https://doi.org/10.1007/978-3-319-07959-2_4 Zobrazit plný text záznamu