Universität zu Köln

Mallach, Sven ORCID: 0000-0001-5335-0678 (2018). Linear ordering based MIP formulations for the vertex separation or pathwidth problem. J. Discret. Algorithms, 52-53. S. 156 - 168. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1570-8675

Full text not available from this repository.

Abstract

We consider the task to compute the pathwidth of a graph which is known to be equivalent to solving the vertex separation problem. The latter is naturally modeled as a linear ordering problem with respect to the vertices of the graph. Present mixed-integer programs for the vertex separation problem express linear orders using either position or set assignment variables. However, as we show, the lower bound on the pathwidth obtained when solving their linear programming relaxations is zero for any directed graph. This is one reason for their limited utility in solving larger instances to optimality. We then present a new formulation that is based on conventional linear ordering variables and a slightly different perspective on the problem. Its relaxation provably delivers non-zero lower bounds for any graph whose pathwidth is non-zero. Further structural results for and extensions to this formulation are discussed. Finally, an experimental evaluation of three mixed-integer programs, each representing one of the different yet existing modeling approaches, displays their potentials and limitations when used to solve the problem to optimality in practice. (C) 2018 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Mallach, Sven UNSPECIFIED orcid.org/0000-0001-5335-0678 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-173676
DOI:	10.1016/j.jda.2018.11.012
Journal or Publication Title:	J. Discret. Algorithms
Volume:	52-53
Page Range:	S. 156 - 168
Date:	2018
Publisher:	ELSEVIER SCIENCE BV
Place of Publication:	AMSTERDAM
ISSN:	1570-8675
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language ALGORITHMS; TREEWIDTH; SEARCH; NUMBER; GRAPHS Multiple languages Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/17367