A variation on the min cut linear arrangement problem
From MaRDI portal
Publication:3785979
DOI10.1007/BF01692067zbMath0643.68094MaRDI QIDQ3785979
Publication date: 1987
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01692067
approximation algorithm; NP-complete; linear-time algorithm; min cut linear arrangement problem; embedding outerplanar graphs into spanning tree
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