Separator-based graph embedding into multidimensional grids with small edge-congestion
From MaRDI portal
Publication:2341722
DOI10.1016/j.dam.2014.11.024zbMath1310.05143arXiv1402.7293MaRDI QIDQ2341722
Publication date: 28 April 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.7293
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A framework for solving VLSI graph layout problems
- On the snake in the box problem
- Finding good approximate vertex and edge partitions is NP-hard
- Some simplified NP-complete graph problems
- Treewidth. Computations and approximations
- Embedding complete \(k\)-ary trees into \(k\)-square 2-D meshes with optimal edge congestion
- Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- A unified framework for off-line permutation routing in parallel networks
- The complexity of congestion-1 embedding in a hypercube
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Efficient Embeddings of Binary Trees in VLSI Arrays
- A Separator Theorem for Planar Graphs
- Universality considerations in VLSI circuits
- New lower bound techniques for VLSI
- A Separator Theorem for Nonplanar Graphs
- Efficient Embeddings of Trees in Hypercubes
- An approach to emulating separable graphs
- Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
- Efficient Embeddings into Hypercube-like Topologies
- Expander flows, geometric embeddings and graph partitioning
- Efficient embeddings of grids into grids
