A variation on the min cut linear arrangement problem

DOI10.1007/BF01692067zbMath0643.68094MaRDI 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 algorithm; NP-complete; linear-time algorithm; min cut linear arrangement problem; embedding outerplanar graphs into spanning tree

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

Related Items

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

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