On minimizing width in linear layouts (Q751660): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q521868
Created claim: Wikidata QID (P12): Q128127009, #quickstatements; #temporary_batch_1722437626092
 
(3 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Ivan Hal Sudborough / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity Results for Bandwidth Minimization / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recontamination does not help to search a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Topological Bandwidth / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of searching a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: One-dimensional logic gate assignment and interval graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3208679 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4159394 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A polynomial algorithm for the min-cut linear arrangement of trees / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q128127009 / rank
 
Normal rank

Latest revision as of 15:58, 31 July 2024

scientific article
Language Label Description Also known as
English
On minimizing width in linear layouts
scientific article

    Statements

    On minimizing width in linear layouts (English)
    0 references
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    computation
    0 references
    finite undirected graphs
    0 references
    search number
    0 references
    bandwidth
    0 references
    cutwidth
    0 references

    Identifiers