On minimizing width in linear layouts
type: Item
instance of: scholarly article
title: On minimizing width in linear layouts
zbMATH Open document ID: 0715.05012
DOI: 10.1016/0166-218X(89)90016-4
author: Fillia Makedon
author: I. H. Sudborough
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: The authors deal with finite undirected graphs with cutwidth 2 or 3. (Cutwidth cw is related to search number s and bandwidth B by: \(CW\leq \lfloor \deg (G)\rfloor \cdot B+1S\leq CW\leq \lfloor \deg (G)\rfloor \cdot (S-1)+1,\) where deg(G) denote the maximal degree of any vertex of G.) Interesting corollary: for \(\deg (G)=3\) the search number and cutwidth are identical. The author shows that these estimates are the best possible. Finally an algorithm operating for graphs with cutwidth 2 in linear time is presented.
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 4177074
zbMATH Keywords: computation
zbMATH Keywords: finite undirected graphs
zbMATH Keywords: search number
zbMATH Keywords: bandwidth
zbMATH Keywords: cutwidth
MaRDI profile type: Publication
cites work: Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
cites work: Complexity Results for Bandwidth Minimization
cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
cites work: Recontamination does not help to search a graph
cites work: Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
cites work: Topological Bandwidth
cites work: The complexity of searching a graph
cites work: One-dimensional logic gate assignment and interval graphs
cites work: Q3208679
cites work: Q4159394
cites work: Q4198056
cites work: A polynomial algorithm for the min-cut linear arrangement of trees
Wikidata QID: Q128127009
description: scientific article; zbMATH DE number 4177074