On the public citation graph
Disjoint Cycles: Integrality Gap, Hardness, and Approximation
0 signed · 42 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jcss.1999.1661openalex-snapshot
On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints
inferredcites →https://doi.org/10.1007/978-3-540-30140-0_18openalex-snapshot
Hardness and Approximation Results for Packing Steiner Trees
inferredcites →https://doi.org/10.1007/b100428openalex-snapshot
Algorithms – ESA 2004 : 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004. Proceedings
inferredcites →https://doi.org/10.1007/bf01200760openalex-snapshot
Packing directed circuits fractionally
inferredcites →https://doi.org/10.1007/bfb0015417openalex-snapshot
Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
inferredcites →https://doi.org/10.1007/pl00009191openalex-snapshot
Approximating Minimum Feedback Sets and Multicuts in Directed Graphs
inferredcites →https://doi.org/10.1016/b978-1-55860-332-5.50013-4openalex-snapshot
Approximation Algorithms for the Loop Cutset Problem
inferredcites →https://doi.org/10.1016/s0022-0000(03)00066-7openalex-snapshot
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
inferredcites →https://doi.org/10.1016/s0167-6377(98)00021-2openalex-snapshot
A primal–dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
inferredcites →https://doi.org/10.1016/s0196-6774(03)00052-xopenalex-snapshot
Packing cycles in undirected graphs
inferredcites →https://doi.org/10.1017/s0963548302005461openalex-snapshot
Packing Digraphs with Directed Closed Trails
inferredcites →https://doi.org/10.1109/focs.2004.10openalex-snapshot
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1137/s0895480195291874openalex-snapshot
Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
inferredcites →https://doi.org/10.1145/1290672.1290683openalex-snapshot
Edge-disjoint paths revisited
inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot
Probabilistic checking of proofs
inferredcites →https://doi.org/10.1145/278298.278306openalex-snapshot
Proof verification and the hardness of approximation problems
inferredcites →https://doi.org/10.1145/335305.335312openalex-snapshot
Randomized metarounding (extended abstract)
inferredcites →https://doi.org/10.5486/pmd.1962.9.1-2.02openalex-snapshot
On the maximal number of disjoint circuits of a graph
inferredcites →https://doi.org/10.5555/1070432.1070510openalex-snapshot
Approximation algorithms for cycle packing problems
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/cpe.70957openalex-snapshot
Two Self‐Stabilizing Algorithms for the Maximal Pentagon Partitioning Problem
inferred← citeshttps://doi.org/10.1007/11496656_33openalex-snapshot
Exact and Approximation Algorithms for DNA Tag Set Design
inferred← citeshttps://doi.org/10.1007/978-3-319-28684-6_11openalex-snapshot
An $$O(\log \mathrm{OPT})$$ O ( log OPT ) -Approximation for Covering/Packing Minor Models of $$\theta _{r}$$ θ r
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_33openalex-snapshot
Parameterized Approximability of the Disjoint Cycle Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-77120-3_28openalex-snapshot
Approximability of Packing Disjoint Cycles
inferred← citeshttps://doi.org/10.1007/978-3-540-78773-0_63openalex-snapshot
Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
inferred← citeshttps://doi.org/10.1007/s00453-017-0313-5openalex-snapshot
An $$O(\log \mathrm {OPT})$$ O ( log OPT ) -Approximation for Covering and Packing Minor Models of $$\theta _r$$ θ r
inferred← citeshttps://doi.org/10.1007/s10878-010-9347-1openalex-snapshot
Packing cycles exactly in polynomial time
inferred← citeshttps://doi.org/10.1016/j.disc.2010.03.009openalex-snapshot
Packing disjoint cycles over vertex cuts
inferred← citeshttps://doi.org/10.1016/j.disc.2012.10.010openalex-snapshot
Covering vertices by a specified number of disjoint cycles, edges and isolated vertices
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.01.008openalex-snapshot
Efficient approximation algorithms for shortest cycles in undirected graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.12.009openalex-snapshot
The transposition median problem is NP-complete
inferred← citeshttps://doi.org/10.1137/060656048openalex-snapshot
Combination Can Be Hard: Approximability of the Unique Coverage Problem
inferred← citeshttps://doi.org/10.1137/100786423openalex-snapshot
Packing Directed Circuits through Prescribed Vertices Bounded Fractionally
inferred← citeshttps://doi.org/10.46298/dmtcs.587openalex-snapshot
Graphs with many vertex-disjoint cycles
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0503057openalex-snapshot
Exact and Approximation Algorithms for DNA Tag Set Design
inferred← citeshttps://doi.org/10.5555/1109557.1109577openalex-snapshot
Combination can be hard: approximability of the unique coverage problem
inferred← citeshttps://doi.org/10.70675/658f0687ze25fz44e7z9761z187dd29af957openalex-snapshot
Structural and algorithmic aspects of partial orderings of graphs
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.