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

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