On Canonical Concurrent Flows, Crossing Number and Graph Expansion

DOI10.1017/S0963548300001383zbMath0817.05022OpenAlexW2080020690MaRDI QIDQ4325335

Farhad Shahrokhi, László A. Székely

Publication date: 30 March 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300001383

zbMATH Keywords

lower boundscrossing numbersgraph extensionconcurrent flow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (2)

Drawings of graphs on surfaces with few crossings ⋮ On the dual distance and the gap of a binary code

Cites Work

• A new polynomial-time algorithm for linear programming
• Compressions and isoperimetric inequalities
• Sparsest cuts and bottlenecks in graphs
• Multiterminal global routing: A deterministic approximation scheme
• Multicommodity flows in planar graphs
• Edge-isoperimetric inequalities in the grid
• A note on the edges of the n-cube
• On forwarding indices of networks
• Isoperimetric numbers of graphs
• The forwarding index of communication networks
• Crossing Number is NP-Complete
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• The maximum concurrent flow problem
• The Forwarding Indices of Random Graphs
• Approximation Algorithms for the Maximum Concurrent Flow Problem
• Bounds for the crossing number of the N‐cube

This page was built for publication: On Canonical Concurrent Flows, Crossing Number and Graph Expansion