A variation on the min cut linear arrangement problem

DOI10.1007/BF01692067zbMath0643.68094OpenAlexW2067096953MaRDI QIDQ3785979

Shai Simonson

Publication date: 1987

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01692067

zbMATH Keywords

approximation algorithmNP-completelinear-time algorithmmin cut linear arrangement problemembedding outerplanar graphs into spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (11)

A Survey on Spanning Tree Congestion ⋮ On embedding graphs in trees ⋮ Routing with critical paths ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Spanning tree congestion of \(k\)-outerplanar graphs ⋮ On the complexity of tree embedding problems ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ Communication tree problems ⋮ Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem ⋮ On spanning tree congestion of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On optimal linear arrangements of trees
• White pebbles help
• The NP-completeness of the bandwidth minimization problem
• Some simplified NP-complete graph problems
• Topological Bandwidth
• Cost Trade-offs in Graph Embeddings, with Applications
• A polynomial algorithm for the min-cut linear arrangement of trees
• The complexity of searching a graph
• Applications of a Planar Separator Theorem
• Graphs That are Almost Binary Trees
• Complexity Results for Bandwidth Minimization
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• Optimal Linear Ordering

This page was built for publication: A variation on the min cut linear arrangement problem