A constant-factor approximation for weighted bond cover

DOI10.1016/j.jcss.2024.103617MaRDI QIDQ6671673FDOQ6671673

Authors: Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos 

Publication date: 27 January 2025

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Recommendations

• Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Hitting forbidden minors: approximation and kernelization
• Hitting forbidden minors: approximation and kernelization

zbMATH Keywords

graph minorsgraph modification problemsprimal-dual methodconstant-factor approximation algorithmsbonds in graphs

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Properties of vertex packing and independence system polyhedra
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Finding odd cycle transversals.
• Graph minors. XX: Wagner's conjecture
• The node-deletion problem for hereditary properties is NP-complete
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Which problems have strongly exponential complexity?
• The extremal function for complete minors
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Title not available (Why is that?)
• Graph minors. V. Excluding a planar graph
• The disjoint paths problem in quadratic time
• Title not available (Why is that?)
• Hitting forbidden minors: approximation and kernelization
• The approximation of maximum subgraph problems
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Hitting diamonds and growing cacti
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Approximation and intractability results for the maximum cut problem and its variants
• Linear recognition of almost interval graphs
• Compression via Matroids
• (Meta) kernelization
• Approximation and kernelization for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs
• On interval routing schemes and treewidth
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• LP-based robust algorithms for noisy minor-free and bounded treewidth graphs
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• Interval vertex deletion admits a polynomial kernel
• Hitting topological minors is FPT
• Losing Treewidth by Separating Subsets
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• Edge degeneracy: algorithmic and structural results
• A tight Erdős-Pósa function for planar minors
• Mimicking Networks and Succinct Representations of Terminal Cuts

Cited In (1)

• Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems

This page was built for publication: A constant-factor approximation for weighted bond cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6671673)