scientific article

Erik D. Demaine, Mohammad Taghi Hajiaghayi

Publication date: 13 October 2014

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

Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)

Related Items (53)

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Towards the Graph Minor Theorems for Directed Graphs ⋮ Complexity of metric dimension on planar graphs ⋮ Graph Minors and Parameterized Algorithm Design ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Quickly deciding minor-closed parameters in general graphs ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ Experiments on data reduction for optimal domination in networks ⋮ Unnamed Item ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ Splitting plane graphs to outerplanarity ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Subexponential algorithms for partial cover problems ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions ⋮ Subexponential parameterized algorithms ⋮ Confronting intractability via parameters ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Fast minor testing in planar graphs ⋮ A linear kernel for a planar connected dominating set ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ Slightly Superexponential Parameterized Problems ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ Unnamed Item ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Bidimensionality and Kernels ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Decomposition of Map Graphs with Applications. ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: