Breaking o(n 1/2 )-approximation algorithms for the edge-disjoint paths problem with congestion two

DOI10.1145/1993636.1993648zbMath1288.68127OpenAlexW1966586808MaRDI QIDQ5419077

Ken-ichi Kawarabayashi, Yusuke Kobayashi

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993648

zbMATH Keywords

disjoint pathsRao-Zhou algorithmwell-linked set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Routing in Undirected Graphs with Constant Congestion

This page was built for publication: Breaking o(n ^1/2 )-approximation algorithms for the edge-disjoint paths problem with congestion two