On the public citation graph

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

0 signed · 99 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.3190130114openalex-snapshot
Graph spanners
inferredcites →https://doi.org/10.1002/net.1975.5.1.45openalex-snapshot
On the Computational Complexity of Combinatorial Problems
inferredcites →https://doi.org/10.1006/jcss.1996.0002openalex-snapshot
Separator Based Sparsification
inferredcites →https://doi.org/10.1006/jcss.1997.1493openalex-snapshot
Faster Shortest-Path Algorithms for Planar Graphs
inferredcites →https://doi.org/10.1006/jcss.1998.1592openalex-snapshot
Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth
inferredcites →https://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1006/jctb.1994.1073openalex-snapshot
Quickly Excluding a Planar Graph
inferredcites →https://doi.org/10.1007/3-540-57273-2_72openalex-snapshot
A fully dynamic data structure for reachability in planar digraphs
inferredcites →https://doi.org/10.1007/978-3-540-75520-3_53openalex-snapshot
Dynamic Plane Transitive Closure
inferredcites →https://doi.org/10.1007/978-3-642-02927-1_32openalex-snapshot
Incompressibility through Colors and IDs
inferredcites →https://doi.org/10.1007/978-3-642-02927-1_59openalex-snapshot
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
inferredcites →https://doi.org/10.1007/978-3-642-15155-2_56openalex-snapshot
Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
inferredcites →https://doi.org/10.1007/978-3-642-16533-7openalex-snapshot
Exact Exponential Algorithms
inferredcites →https://doi.org/10.1007/978-3-642-31594-7_48openalex-snapshot
Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
inferredcites →https://doi.org/10.1007/978-3-642-31594-7_57openalex-snapshot
A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
inferredcites →https://doi.org/10.1007/bf01758778openalex-snapshot
A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph
inferredcites →https://doi.org/10.1007/bf02189308openalex-snapshot
On sparse spanners of weighted graphs
inferredcites →https://doi.org/10.1007/pl00009223openalex-snapshot
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs
inferredcites →https://doi.org/10.1007/s00453-007-9130-6openalex-snapshot
An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
inferredcites →https://doi.org/10.1007/s00453-012-9662-2openalex-snapshot
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
inferredcites →https://doi.org/10.1007/s00453-016-0249-1openalex-snapshot
Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices
inferredcites →https://doi.org/10.1007/s00493-008-2140-4openalex-snapshot
Linearity of grid minors in treewidth with applications through bidimensionality
inferredcites →https://doi.org/10.1016/0020-0190(89)90039-2openalex-snapshot
The Steiner problem with edge lengths 1 and 2
inferredcites →https://doi.org/10.1016/j.ipl.2013.12.001openalex-snapshot
An O⁎(1.84k) parameterized algorithm for the multiterminal cut problem
inferredcites →https://doi.org/10.1016/j.jcss.2009.04.001openalex-snapshot
On problems without polynomial kernels
inferredcites →https://doi.org/10.1016/j.jcss.2010.06.007openalex-snapshot
Infeasibility of instance compression and succinct PCPs for NP
inferredcites →https://doi.org/10.1016/j.jcss.2012.02.004openalex-snapshot
Catalan structures and dynamic programming in H-minor-free graphs
inferredcites →https://doi.org/10.1016/j.tcs.2005.10.007openalex-snapshot
Parameterized graph separation problems
inferredcites →https://doi.org/10.1016/j.tcs.2011.09.014openalex-snapshot
Faster approximation schemes and parameterized algorithms on (odd-) H -minor-free graphs
inferredcites →https://doi.org/10.1016/s1571-0653(04)00353-1openalex-snapshot
Treewidth of planar graphs: connections with duality
inferredcites →https://doi.org/10.1016/s1571-0661(04)00301-9openalex-snapshot
Parameterized Complexity
inferredcites →https://doi.org/10.1093/acprof:oso/9780198566076.001.0001openalex-snapshot
Invitation to Fixed-Parameter Algorithms
inferredcites →https://doi.org/10.1093/acprof:oso/9780198566076.003.0004openalex-snapshot
VERTEX COVER—AN ILLUSTRATIVE EXAMPLE
inferredcites →https://doi.org/10.1093/comjnl/bxm033openalex-snapshot
The Bidimensionality Theory and Its Algorithmic Applications
inferredcites →https://doi.org/10.1109/focs.2012.46openalex-snapshot
Representative Sets and Irrelevant Vertices: New Tools for Kernelization
inferredcites →https://doi.org/10.1109/focs.2014.37openalex-snapshot
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
inferredcites →https://doi.org/10.1109/focs.2018.00052openalex-snapshot
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs
inferredcites →https://doi.org/10.1137/0109047openalex-snapshot
Multi-Terminal Network Flows
inferredcites →https://doi.org/10.1137/0132071openalex-snapshot
The Rectilinear Steiner Tree Problem is $NP$-Complete
inferredcites →https://doi.org/10.1137/090772873openalex-snapshot
Twice-Ramanujan Sparsifiers
inferredcites →https://doi.org/10.1137/130927115openalex-snapshot
New Limits to Classical and Quantum Instance Compression
inferredcites →https://doi.org/10.1137/17m1151225openalex-snapshot
Refined Vertex Sparsifiers of Planar Graphs
inferredcites →https://doi.org/10.1137/20m1353782openalex-snapshot
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
inferredcites →https://doi.org/10.1137/s0097539792225297openalex-snapshot
The Complexity of Multiterminal Cuts
inferredcites →https://doi.org/10.1137/s0097539792236237openalex-snapshot
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
inferredcites →https://doi.org/10.1137/s0097539793253565openalex-snapshot
The Vertex-Disjoint Menger Problem in Planar Graphs
inferredcites →https://doi.org/10.1137/s0097539794269072openalex-snapshot
Separator-Based Sparsification II: Edge and Vertex Connectivity
inferredcites →https://doi.org/10.1145/1101821.1101823openalex-snapshot
Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
inferredcites →https://doi.org/10.1145/1132516.1132620openalex-snapshot
A subset spanner for Planar graphs, with application to subset TSP
inferredcites →https://doi.org/10.1145/1541885.1541892openalex-snapshot
An O ( n log n ) approximation scheme for Steiner tree in planar graphs
inferredcites →https://doi.org/10.1145/174644.174650openalex-snapshot
Approximation algorithms for NP-complete problems on planar graphs
inferredcites →https://doi.org/10.1145/1806689.1806769openalex-snapshot
An improved LP-based approximation for steiner tree
inferredcites →https://doi.org/10.1145/1993636.1993679openalex-snapshot
Improved algorithms for min cut and max flow in undirected planar graphs
inferredcites →https://doi.org/10.1145/2027216.2027219openalex-snapshot
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
inferredcites →https://doi.org/10.1145/237814.237827openalex-snapshot
Approximating s-t minimum cuts in Õ ( n 2 ) time
inferredcites →https://doi.org/10.1145/2432622.2432628openalex-snapshot
Steiner Tree Approximation via Iterative Randomized Rounding
inferredcites →https://doi.org/10.1145/2488608.2488702openalex-snapshot
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
inferredcites →https://doi.org/10.1145/2635810openalex-snapshot
Compression via Matroids
inferredcites →https://doi.org/10.1145/2650261openalex-snapshot
Kernelization Lower Bounds Through Colors and IDs
inferredcites →https://doi.org/10.1145/265910.265914openalex-snapshot
Sparsification—a technique for speeding up dynamic graph algorithms
inferredcites →https://doi.org/10.1145/2925416openalex-snapshot
On Problems as Hard as CNF-SAT
inferredcites →https://doi.org/10.1145/2973749openalex-snapshot
(Meta) Kernelization
inferredcites →https://doi.org/10.1145/320211.320215openalex-snapshot
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
inferredcites →https://doi.org/10.1145/780542.780570openalex-snapshot
The computational complexity of some julia sets
inferredcites →https://doi.org/10.1287/moor.1030.0086openalex-snapshot
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
inferredcites →https://doi.org/10.1287/moor.12.4.634openalex-snapshot
Send-and-Split Method for Minimum-Concave-Cost Network Flows
inferredcites →https://doi.org/10.4064/fm-17-1-152-170openalex-snapshot
Sur les rétractes
inferredcites →https://doi.org/10.4230/dagrep.2.6.26openalex-snapshot
Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)
inferredcites →https://doi.org/10.4230/lipics.esa.2017.44openalex-snapshot
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs
inferredcites →https://doi.org/10.4230/lipics.ipec.2018.0openalex-snapshot
Front Matter, Table of Contents, Preface, Conference Organization
inferredcites →https://doi.org/10.4230/lipics.stacs.2012.iopenalex-snapshot
Frontmatter, Foreword, Conference Organization, External Reviewers, Table of Contents
inferredcites →https://doi.org/10.4230/lipics.stacs.2013.353openalex-snapshot
Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
inferredcites →https://doi.org/10.5555/1873601.1873644openalex-snapshot
Bidimensionality and kernels
inferredcites →https://doi.org/10.5555/2095116.2095170openalex-snapshot
A polynomial-time approximation scheme for planar multiway cut
inferredcites →https://doi.org/10.5555/2805875.2805976openalex-snapshot
On sparse spanners of weighted graphs

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-030-86838-3_1openalex-snapshot
Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
inferred← citeshttps://doi.org/10.1007/s00453-016-0244-6openalex-snapshot
Linear Kernels for Outbranching Problems in Sparse Digraphs
inferred← citeshttps://doi.org/10.1016/j.cosrev.2025.100796openalex-snapshot
Parameterized algorithms on geometric intersection graphs
inferred← citeshttps://doi.org/10.1016/j.cosrev.2026.101035openalex-snapshot
Quo Vadis, Kernelization?
inferred← citeshttps://doi.org/10.1016/j.dam.2021.05.021openalex-snapshot
Revising Johnson’s table for the 21st century
inferred← citeshttps://doi.org/10.1016/j.jcss.2024.103532openalex-snapshot
Preprocessing to reduce the search space: Antler structures for feedback vertex set
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.10.023openalex-snapshot
A relaxation of the Directed Disjoint Paths problem: A global congestion metric helps
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00044openalex-snapshot
Planar Disjoint Paths, Treewidth, and Kernels
inferred← citeshttps://doi.org/10.1137/1.9781611977073.81openalex-snapshot
Planar Multiway Cut with Terminals on Few Faces
inferred← citeshttps://doi.org/10.1137/1.9781611977073.82openalex-snapshot
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H -Minor-Free Graphs
inferred← citeshttps://doi.org/10.1137/1.9781611977073.83openalex-snapshot
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
inferred← citeshttps://doi.org/10.1137/19m1262504openalex-snapshot
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
inferred← citeshttps://doi.org/10.1137/20m1353782openalex-snapshot
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
inferred← citeshttps://doi.org/10.1137/20m1355902openalex-snapshot
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
inferred← citeshttps://doi.org/10.1137/22m152058xopenalex-snapshot
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
inferred← citeshttps://doi.org/10.1145/3357713.3384250openalex-snapshot
An exponential time parameterized algorithm for planar disjoint paths
inferred← citeshttps://doi.org/10.1145/3447584openalex-snapshot
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
inferred← citeshttps://doi.org/10.1145/3483425openalex-snapshot
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
inferred← citeshttps://doi.org/10.1145/3519935.3520021openalex-snapshot
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
inferred← citeshttps://doi.org/10.1145/3519935.3520049openalex-snapshot
Bypassing the surface embedding: approximation schemes for network design in minor-free graphs
inferred← citeshttps://doi.org/10.1145/3798129.3800858openalex-snapshot
Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs
inferred← citeshttps://doi.org/10.1287/moor.2023.0231openalex-snapshot
Tight Running Times for Minimum ℓ q -Norm Load Balancing: Beyond Exponential Dependencies on 1/ϵ
inferred← citeshttps://doi.org/10.37236/11063openalex-snapshot
Bounds on Half Graph Orders in Powers of Sparse Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.2107.06261openalex-snapshot
Tight running times for minimum $\ell_q$-norm load balancing: beyond exponential dependencies on $1/ε$
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.