On the public citation graph
Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
0 signed · 66 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.1007/3-540-56939-1_60openalex-snapshot
The approximation of maximum subgraph problems
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/bf00290149openalex-snapshot
Ramsey numbers and an approximation algorithm for the vertex cover problem
inferredcites →https://doi.org/10.1016/0022-0000(80)90060-4openalex-snapshot
The node-deletion problem for hereditary properties is NP-complete
inferredcites →https://doi.org/10.1016/0022-0000(91)90023-xopenalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1016/0166-218x(83)90080-xopenalex-snapshot
Efficient bounds for the stable set, vertex cover and set packing problems
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/s0304-0208(08)73101-3openalex-snapshot
A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.5555/314464.314514openalex-snapshot
Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jagm.1998.0995openalex-snapshot
Approximating Node-Deletion Problems for Matroidal Properties
inferred← citeshttps://doi.org/10.1006/jagm.2000.1137openalex-snapshot
Wavelength Conversion in Optical Networks
inferred← citeshttps://doi.org/10.1007/0-306-48332-7_135openalex-snapshot
Biquadratic assignment problem; Graph coloring; Graph planarization; Greedy randomized adaptive search procedures; Quadratic assignment problem; Quadratic semi-assignment problem; Three-index assignment problemBiquadratic assignment problem; Graph coloring; Graph planarization; Greedy randomized…
inferred← citeshttps://doi.org/10.1007/11496915_5openalex-snapshot
Disjoint Cycles: Integrality Gap, Hardness, and Approximation
inferred← citeshttps://doi.org/10.1007/11523468_76openalex-snapshot
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?
inferred← citeshttps://doi.org/10.1007/3-540-44929-9_15openalex-snapshot
On the Hardness of Approximating Some NP-Optimization Problems Related to Minimum Linear Ordering Problem
inferred← citeshttps://doi.org/10.1007/3-540-61310-2_12openalex-snapshot
Primal-dual approximation algorithms for feedback problems in planar graphs
inferred← citeshttps://doi.org/10.1007/3-540-61680-2_54openalex-snapshot
A unified local ratio approximation of node-deletion problems
inferred← citeshttps://doi.org/10.1007/3-540-63165-8_228openalex-snapshot
A primal-dual approach to approximation of node-deletion problems for matroidal properties
inferred← citeshttps://doi.org/10.1007/978-1-4613-3437-8_21openalex-snapshot
A Pseudo ∈-Approximate Algorithm For Feedback Vertex Set
inferred← citeshttps://doi.org/10.1007/978-3-030-39881-1_24openalex-snapshot
Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs
inferred← citeshttps://doi.org/10.1007/978-3-030-48966-3_13openalex-snapshot
Polynomial Time Algorithms for Tracking Path Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-08001-7_3openalex-snapshot
Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
inferred← citeshttps://doi.org/10.1007/978-3-540-27798-9_17openalex-snapshot
An Approximation Algorithm for Weighted Weak Vertex Cover Problem in Undirected Graphs
inferred← citeshttps://doi.org/10.1007/bfb0053963openalex-snapshot
One for the price of two: A unified approach for approximating covering problems
inferred← citeshttps://doi.org/10.1007/s00224-014-9565-5openalex-snapshot
Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
inferred← citeshttps://doi.org/10.1007/s004530010009openalex-snapshot
One for the Price of Two: a Unified Approach for Approximating Covering Problems
inferred← citeshttps://doi.org/10.1007/s10107-024-02179-9openalex-snapshot
Polyhedral aspects of feedback vertex set and pseudoforest deletion set
inferred← citeshttps://doi.org/10.1007/s10255-004-0195-6openalex-snapshot
A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs
inferred← citeshttps://doi.org/10.1007/s10732-013-9224-zopenalex-snapshot
Applying local search to the feedback vertex set problem
inferred← citeshttps://doi.org/10.1016/0020-0190(96)00094-4openalex-snapshot
A note on approximation of the vertex cover and feedback vertex set problems — Unified approach
inferred← citeshttps://doi.org/10.1016/j.cor.2005.01.014openalex-snapshot
A constraint programming approach to cutset problems
inferred← citeshttps://doi.org/10.1016/j.disopt.2009.01.004openalex-snapshot
On the feedback vertex set polytope of a series–parallel graph
inferred← citeshttps://doi.org/10.1016/j.ic.2012.10.017openalex-snapshot
Primal-dual approximation algorithms for Node-Weighted Steiner Forest on planar graphs
inferred← citeshttps://doi.org/10.1016/j.ipl.2004.12.008openalex-snapshot
A linear time algorithm for the minimum Weighted Feedback Vertex Set on diamonds
inferred← citeshttps://doi.org/10.1016/j.jctb.2012.05.004openalex-snapshot
Disjoint cycles intersecting a set of vertices
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.06.009openalex-snapshot
Approximating the minimum weight weak vertex cover
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.11.009openalex-snapshot
Min (a)cyclic feedback vertex sets and min ones monotone 3-SAT
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.10.026openalex-snapshot
Approximability of the independent feedback vertex set problem for bipartite graphs
inferred← citeshttps://doi.org/10.1016/s0020-0190(02)00265-xopenalex-snapshot
Minimum feedback vertex set and acyclic coloring
inferred← citeshttps://doi.org/10.1016/s0020-0190(02)00491-xopenalex-snapshot
Combinatorial algorithms for feedback problems in directed graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(03)00444-xopenalex-snapshot
On approximability of linear ordering and related NP-optimization problems on graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(98)00035-3openalex-snapshot
A unified approximation algorithm for node-deletion problems
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00180-8openalex-snapshot
Solving the feedback vertex set problem on undirected graphs
inferred← citeshttps://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
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00043-2openalex-snapshot
Approximating minimum feedback vertex sets in hypergraphs
inferred← citeshttps://doi.org/10.1023/a:1009736921890openalex-snapshot
A Greedy Randomized Adaptive Search Procedure for the Feedback Vertex Set Problem
inferred← citeshttps://doi.org/10.1051/ita:2001121openalex-snapshot
On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
inferred← citeshttps://doi.org/10.1109/sfcs.1996.548490openalex-snapshot
An 8-approximation algorithm for the subset feedback vertex set problem
inferred← citeshttps://doi.org/10.1137/16m1070670openalex-snapshot
Inapproximability of $H$-Transversal/Packing
inferred← citeshttps://doi.org/10.1137/s0097539796305109openalex-snapshot
Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
inferred← citeshttps://doi.org/10.1145/1290672.1290685openalex-snapshot
Approximation algorithms and hardness results for cycle packing problems
inferred← citeshttps://doi.org/10.1145/1978782.1978784openalex-snapshot
How well can primal-dual and local-ratio algorithms perform?
inferred← citeshttps://doi.org/10.1145/2897518.2897635openalex-snapshot
Approximating connectivity domination in weighted bounded-genus graphs
inferred← citeshttps://doi.org/10.1159/000022781openalex-snapshot
Automatic Selection ofLoop Breakers for GeneticLinkage Analysis
inferred← citeshttps://doi.org/10.1184/r1/6606422openalex-snapshot
Inapproximability of $H$-Transversal/Packing
inferred← citeshttps://doi.org/10.1613/jair.638openalex-snapshot
Randomized Algorithms for the Loop Cutset Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1208.5907openalex-snapshot
Choose Outsiders First: a mean 2-approximation random algorithm for covering problems
inferred← citeshttps://doi.org/10.48550/arxiv.1408.1483openalex-snapshot
Random Algorithms for the Loop Cutset Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1809.01998openalex-snapshot
Min (A)cyclic Feedback Vertex Sets and Min Ones Monotone 3-SAT
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.