On minimum cuts and the linear arrangement problem

In this paper we examine the problem of finding minimum cuts in finite graphs with the side constraint that the vertex sets inducing these cuts must be of a given cardinality. As it turns out, this computation is of interest not only from a combinatorial perspective but also from a practical one, pe...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2000-07, Vol.103 (1), p.127-139
Main Authors: Horton, S.B., Parker, R.Gary, Borie, R.B.
Format: Article
Language:English
Subjects:
Bounds
Combinatorics
Combinatorics. Ordered structures
Cuts
Exact sciences and technology
Graph theory
Linear arrangement
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we examine the problem of finding minimum cuts in finite graphs with the side constraint that the vertex sets inducing these cuts must be of a given cardinality. As it turns out, this computation is of interest not only from a combinatorial perspective but also from a practical one, pertaining to the linear arrangement value of graphs. We look at some graph classes where these cuts can be efficiently computed (in general this computation is NP-hard) as well as some cases where their value can be determined in closed form.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(00)00173-6