Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
From MaRDI portal
Publication:3455210
DOI10.1145/1101821.1101823zbMath1326.05152OpenAlexW2158584754WikidataQ56338015 ScholiaQ56338015MaRDI QIDQ3455210
Dimitrios M. Thilikos, Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi Hajiaghayi
Publication date: 4 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1101821.1101823
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Combing a Linkage in an Annulus, Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, Faster algorithms for cycle hitting problems on disk graphs, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, A survey of parameterized algorithms and the complexity of edge modification, Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, On the Parameterized Complexity of the Expected Coverage Problem, Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, A Retrospective on (Meta) Kernelization, Contraction bidimensionality of geometric intersection graphs, (Total) vector domination for graphs with bounded branchwidth, Adapting the directed grid theorem into an \textsf{FPT} algorithm, On the parameterized complexity of the expected coverage problem, Towards the Graph Minor Theorems for Directed Graphs, Untangling two systems of noncrossing curves, Approximate tree decompositions of planar graphs in linear time, Graph Minors and Parameterized Algorithm Design, Parameterized Complexity for Domination Problems on Degenerate Graphs, Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, Genus characterizes the complexity of certain graph problems: Some tight results, A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs, Unnamed Item, Linear kernels for outbranching problems in sparse digraphs, Parameterized and approximation algorithms for the load coloring problem, Improved induced matchings in sparse graphs, A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three, Approximation Algorithms for Euler Genus and Related Problems, A \(9k\) kernel for nonseparating independent set in planar graphs, Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}, On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Effective computation of immersion obstructions for unions of graph classes, On the excluded minor structure theorem for graphs of large tree-width, Adapting the Directed Grid Theorem into an FPT Algorithm, On the parameterized complexity of the acyclic matching problem, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Capacitated Domination and Covering: A Parameterized Perspective, An Improved Algorithm for Finding Cycles Through Elements, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Subexponential algorithms for partial cover problems, Local search: is brute-force avoidable?, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Subexponential parameterized algorithms, Guard games on graphs: keep the intruder out!, Faster parameterized algorithms for minor containment, Confronting intractability via parameters, Spanners in sparse graphs, Implicit branching and parameterized partial cover problems, 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, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, First-Order Model-Checking in Random Graphs and Complex Networks, Computing cooperative solution concepts in coalitional skill games, Reducing CMSO model checking to highly connected graphs, FPT algorithms for domination in sparse graphs and beyond, Towards fixed-parameter tractable algorithms for abstract argumentation, A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families, Dynamic programming and planarity: improved tree-decomposition based algorithms, Slightly Superexponential Parameterized Problems, Unnamed Item, Contraction obstructions for treewidth, Unnamed Item, Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs, Optimality program in segment and string graphs, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, A $c^k n$ 5-Approximation Algorithm for Treewidth, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, A polynomial kernel for trivially perfect editing, Covering nearly surface-embedded graphs with a fixed number of balls, The complexity of tree partitioning, A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem, Parameterized complexity of geometric covering problems having conflicts, A Subexponential Parameterized Algorithm for Proper Interval Completion, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Bidimensionality and Kernels, A relaxation of the directed disjoint paths problem: a global congestion metric helps, Decomposition of Map Graphs with Applications., On width measures and topological problems on semi-complete digraphs, Exploring the Subexponential Complexity of Completion Problems, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, On approximate preprocessing for domination and hitting subgraphs with connected deletion sets, Structural sparsity of complex networks: bounded expansion in random models and real-world graphs, Planar k-Path in Subexponential Time and Polynomial Space, Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs, Planar Capacitated Dominating Set Is W[1-Hard], Improved Induced Matchings in Sparse Graphs, Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor, Computational study on planar dominating set problem, Subexponential parameterized algorithms for graphs of polynomial growth, Contraction-Bidimensionality of Geometric Intersection Graphs, Lossy Kernels for Hitting Subgraphs, Dynamic programming for graphs on surfaces, Parameterized Algorithms for Generalized Domination, Finding, hitting and packing cycles in subexponential time on unit disk graphs, Twin-width and polynomial kernels, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Capacitated domination: problem complexity and approximation algorithms, Faster parameterized algorithms for deletion to split graphs
