On the public citation graph

A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

https://doi.org/10.1145/2893472
0 signed · 72 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/jgt.3190120314openalex-snapshot
Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
inferredcites →https://doi.org/10.1006/jcss.1998.1579openalex-snapshot
Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks
inferredcites →https://doi.org/10.1007/3-540-45535-3_2openalex-snapshot
Strongly Polynomial Algorithms for the Unsplittable Flow Problem
inferredcites →https://doi.org/10.1007/3-540-56939-1_62openalex-snapshot
Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
inferredcites →https://doi.org/10.1007/978-1-4684-2001-2openalex-snapshot
Complexity of Computer Computations
inferredcites →https://doi.org/10.1007/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1007/978-3-642-15369-3_21openalex-snapshot
An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs
inferredcites →https://doi.org/10.1007/bf02523685openalex-snapshot
Primal-dual approximation algorithms for integral flow and multicut in trees
inferredcites →https://doi.org/10.1007/bf02579324openalex-snapshot
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
inferredcites →https://doi.org/10.1007/s00453-005-1172-zopenalex-snapshot
Combinatorial Algorithms for the Unsplittable Flow Problem
inferredcites →https://doi.org/10.1007/s00493-010-2455-9openalex-snapshot
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs
inferredcites →https://doi.org/10.1007/s10107-002-0370-6openalex-snapshot
Approximating disjoint-path problems using packing integer programs
inferredcites →https://doi.org/10.1016/0095-8956(86)90030-4openalex-snapshot
Graph minors. V. Excluding a planar graph
inferredcites →https://doi.org/10.1016/s0167-5060(08)70459-xopenalex-snapshot
On Connectivity Properties of Eulerian Digraphs
inferredcites →https://doi.org/10.1016/s0167-5060(08)70504-1openalex-snapshot
A Reduction Method for Edge-Connectivity in Graphs
inferredcites →https://doi.org/10.1016/s0167-6377(03)00022-1openalex-snapshot
Reconstructing edge-disjoint paths
inferredcites →https://doi.org/10.1017/cbo9780511581274openalex-snapshot
Concentration of Measure for the Analysis of Randomized Algorithms
inferredcites →https://doi.org/10.1080/00029890.1962.11989827openalex-snapshot
College Admissions and the Stability of Marriage
inferredcites →https://doi.org/10.1109/focs.2004.27openalex-snapshot
Edge-Disjoint Paths in Planar Graphs
inferredcites →https://doi.org/10.1109/focs.2010.33openalex-snapshot
Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
inferredcites →https://doi.org/10.1109/focs.2011.30openalex-snapshot
Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
inferredcites →https://doi.org/10.1109/sfcs.1994.365675openalex-snapshot
On-line admission control and circuit routing for high performance computing and communication
inferredcites →https://doi.org/10.1109/sfcs.1994.365733openalex-snapshot
The geometry of graphs and some of its algorithmic applications
inferredcites →https://doi.org/10.1109/sfcs.1995.492462openalex-snapshot
Disjoint paths in densely embedded graphs
inferredcites →https://doi.org/10.1109/sfcs.1996.548467openalex-snapshot
Short paths in expander graphs
inferredcites →https://doi.org/10.1109/sfcs.2002.1181881openalex-snapshot
Minimizing congestion in general networks
inferredcites →https://doi.org/10.1109/sfcs.2005.18openalex-snapshot
An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs
inferredcites →https://doi.org/10.1137/0205048openalex-snapshot
On the Complexity of Timetable and Multicommodity Flow Problems
inferredcites →https://doi.org/10.1137/050636899openalex-snapshot
Hardness of the Undirected Congestion Minimization Problem
inferredcites →https://doi.org/10.1137/060674442openalex-snapshot
Edge-Disjoint Paths in Planar Graphs with Constant Congestion
inferredcites →https://doi.org/10.1137/080715093openalex-snapshot
Edge Disjoint Paths in Moderately Connected Graphs
inferredcites →https://doi.org/10.1137/1.9780898715583openalex-snapshot
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
inferredcites →https://doi.org/10.1137/s0097539700366103openalex-snapshot
Edge-Disjoint Paths in Expander Graphs
inferredcites →https://doi.org/10.1137/s0097539792232021openalex-snapshot
Existence and Construction of Edge-Disjoint Paths on Expander Graphs
inferredcites →https://doi.org/10.1137/s0097539793243016openalex-snapshot
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
inferredcites →https://doi.org/10.1137/s0097539794285983openalex-snapshot
An O (log k ) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
inferredcites →https://doi.org/10.1145/1007352.1007383openalex-snapshot
The all-or-nothing multicommodity flow problem
inferredcites →https://doi.org/10.1145/1060590.1060618openalex-snapshot
Multicommodity flow, well-linked terminals, and routing problems
inferredcites →https://doi.org/10.1145/1060590.1060632openalex-snapshot
Hardness of the undirected edge-disjoint paths problem
inferredcites →https://doi.org/10.1145/1183907.1183910openalex-snapshot
Logarithmic hardness of the undirected edge-disjoint paths problem
inferredcites →https://doi.org/10.1145/1273340.1273343openalex-snapshot
Multicommodity demand flow in a tree and packing integer programs
inferredcites →https://doi.org/10.1145/1374376.1374442openalex-snapshot
On partitioning graphs via single commodity flows
inferredcites →https://doi.org/10.1145/1502793.1502794openalex-snapshot
Expander flows, geometric embeddings and graph partitioning
inferredcites →https://doi.org/10.1145/1538902.1538903openalex-snapshot
Graph partitioning using single commodity flows
inferredcites →https://doi.org/10.1145/1993636.1993648openalex-snapshot
Breaking o(n 1/2 )-approximation algorithms for the edge-disjoint paths problem with congestion two
inferredcites →https://doi.org/10.1145/2213977.2214054openalex-snapshot
Routing in undirected graphs with constant congestion
inferredcites →https://doi.org/10.1145/2438645.2438648openalex-snapshot
An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
inferredcites →https://doi.org/10.1145/2591796.2591813openalex-snapshot
Polynomial bounds for the grid-minor theorem
inferredcites →https://doi.org/10.1145/331524.331526openalex-snapshot
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
inferredcites →https://doi.org/10.1287/moor.25.2.255.12228openalex-snapshot
Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
inferredcites →https://doi.org/10.4086/toc.2006.v002a007openalex-snapshot
inferredcites →https://doi.org/10.4230/lipics.icalp.2017.54openalex-snapshot
Finding Detours is Fixed-Parameter Tractable
inferredcites →https://doi.org/10.5555/313651.313820openalex-snapshot
Improved bounds for all optical routing

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-319-71840-8_5openalex-snapshot
Planar Digraphs
inferred← citeshttps://doi.org/10.1007/978-3-319-94776-1_2openalex-snapshot
Exact Algorithms for Finding Partial Edge-Disjoint Paths
inferred← citeshttps://doi.org/10.1007/s00224-025-10252-9openalex-snapshot
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
inferred← citeshttps://doi.org/10.1007/s00493-021-4743-yopenalex-snapshot
Packing Directed Circuits Quarter-Integrally
inferred← citeshttps://doi.org/10.1093/imrn/rnaa332openalex-snapshot
∞-Operads as Analytic Monads
inferred← citeshttps://doi.org/10.1109/focs.2014.54openalex-snapshot
Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00108openalex-snapshot
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00111openalex-snapshot
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
inferred← citeshttps://doi.org/10.1137/130932326openalex-snapshot
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs
inferred← citeshttps://doi.org/10.1137/17m1146580openalex-snapshot
New Hardness Results for Routing on Disjoint Paths
inferred← citeshttps://doi.org/10.1137/17m1150694openalex-snapshot
Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs
inferred← citeshttps://doi.org/10.1145/2820609openalex-snapshot
Polynomial Bounds for the Grid-Minor Theorem
inferred← citeshttps://doi.org/10.1145/3055399.3055411openalex-snapshot
New hardness results for routing on disjoint paths
inferred← citeshttps://doi.org/10.1145/3188745.3188772openalex-snapshot
Almost polynomial hardness of node-disjoint paths in grids
inferred← citeshttps://doi.org/10.1145/3543507.3583432openalex-snapshot
Worst-Case Welfare of Item Pricing in the Tollbooth Problem
inferred← citeshttps://doi.org/10.4086/toc.2017.v013a020openalex-snapshot
inferred← citeshttps://doi.org/10.4086/toc.2021.v017a006openalex-snapshot
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2018.38openalex-snapshot
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2019.46openalex-snapshot
Algorithmic Properties of Sparse Digraphs
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.