scientific article; zbMATH DE number 7525474

DOI10.4230/LIPICS.ESA.2019.37MaRDI QIDQ5075776zbMATH OpenFDO

Authors Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Ali Vakilian, Andrew van der Poel, Blair D. Sullivan

Publication date 11 May 2022

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

zbMATH Keywords

approximation algorithmsgraph editingstructural rounding

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximating V<scp>ertex</scp> C<scp>over</scp> using Structural Rounding
• Approximation algorithms for graph approximation problems
• Approximation algorithms for approximating graphs with bounded number of connected components
• scientific article; zbMATH DE number 1405893
• The structure and number of global roundings of a graph
• The structure and number of global roundings of a graph
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• Approximation algorithms for constructing some required structures in digraphs
• scientific article; zbMATH DE number 1839472
• A rounding algorithm for approximating minimum Manhattan networks

Cites work

• A near-optimal planarization algorithm
• A new approach for approximating node deletion problems
• A parameterized algorithm for bounded-degree vertex deletion
• A survey of graph edit distance
• A unified approximation algorithm for node-deletion problems
• Edge-editing to a dense and a sparse graph class
• Editing graphs into few cliques: complexity, approximation, and kernelization schemes
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Inapproximability of \(H\)-transversal/packing
• Losing Treewidth by Separating Subsets
• Node-and edge-deletion NP-complete problems
• Node-Deletion NP-Complete Problems
• Obtaining a planar graph by vertex deletion
• Parameterized and Exact Computation
• Parameterized coloring problems on chordal graphs
• Parameterized Graph Editing with Chosen Vertex Degrees
• Partitioning a graph into small pieces with applications to path transversal
• Planarity Allowing Few Error Vertices in Linear Time
• Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
• Semi-online preemptive scheduling: one algorithm for all variants
• Smallest-last ordering and clustering and graph coloring algorithms
• Sparsity. Graphs, structures, and algorithms
• The approximation of maximum subgraph problems
• The graph crossing number and its variants: a survey
• The node-deletion problem for hereditary properties is NP-complete
• The parameterized complexity of editing graphs for bounded degeneracy
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Tight running time lower bounds for vertex deletion problems

Cited in

(10)

• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• Approximating V<scp>ertex</scp> C<scp>over</scp> using Structural Rounding
• Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
• Approximating power node-deletion problems
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Bicriteria \textsf{FPT}-approximation algorithms for vertex deletion to bounded degeneracy graphs
• FPT approximations for packing and covering problems parameterized by elimination distance and even less
• Bicriteria FPT-approximation algorithms for vertex deletion to bounded degeneracy graphs
• Efficient parameterized approximation

This page was built for publication:

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