scientific article; zbMATH DE number 7378613

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.1zbMath1499.68395arXiv1707.04908MaRDI QIDQ5009491

Daniel Lokshtanov, Meirav Zehavi, Pranabendu Misra, Akanksha Agrawal, Saket Saurabh

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1707.04908

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximation algorithmsseparatorplanar-\(F\)-deletion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Signed and weighted graphs (05C22)

Related Items (5)

Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Structural parameterizations with modulator oblivion ⋮ Erdős-Pósa property of chordless cycles and its applications ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Completely separable graphs
• Graph minors. V. Excluding a planar graph
• On diameters and radii of bridged graphs
• The node-deletion problem for hereditary properties is NP-complete
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Graph minors. XIII: The disjoint paths problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Rank-width: algorithmic and structural results
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Hitting Forbidden Minors: Approximation and Kernelization
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Hitting Diamonds and Growing Cacti
• Approximating the k-multicut problem
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• A linear-time approximation algorithm for the weighted vertex cover problem
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Approximation and Kernelization for Chordal Vertex Deletion
• LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
• The approximation of maximum subgraph problems
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Properties of vertex packing and independence system polyhedra
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximating rank-width and clique-width quickly
• Losing Treewidth by Separating Subsets
• Bidimensionality and Geometric Graphs
• On cliques in graphs

This page was built for publication: