FPT algorithms for domination in sparse graphs and beyond

DOI10.1016/J.TCS.2018.10.030MaRDI QIDQ1740694zbMATH OpenOpenAlexWikidataFDO

Authors Jan Arne Telle, Yngve Villanger

Publication date 2 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.10.030

zbMATH Keywords

dominationparameterized algorithmbiclique-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Recommendations

• FPT algorithms for domination in biclique-free graphs
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Domination problems in nowhere-dense classes of graphs
• Dominating set is fixed parameter tractable in claw-free graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A family of regular graphs of girth 5
• Approximation algorithms for combinatorial problems
• Domination problems in nowhere-dense classes of graphs
• FPT algorithms for connected feedback vertex set
• First order properties on nowhere dense structures
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Fundamentals of parameterized complexity
• Incompressibility through Colors and IDs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• On nowhere dense graphs
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Parametrized complexity theory.
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Structural Properties of Sparse Graphs
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• The parameterized complexity of \(k\)-biclique

Cited in

(18)

• Twin-width and polynomial kernels
• FPT algorithms for domination in biclique-free graphs
• Harary polynomials
• scientific article; zbMATH DE number 7310159 (Why is no real title available?)
• Sparse dominance queries for many points in optimal time and space
• An FPT Algorithm for Minimum Additive Spanner Problem.
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Max-SAT with cardinality constraint parameterized by the number of clauses
• Constant-factor approximation of the domination number in sparse graphs
• Domination above \(r\)-independence: does sparseness help?
• On the Parameterized Complexity of [1,j]-Domination Problems
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• Spy game: FPT-algorithm, hardness and graph products
• Domination problems in nowhere-dense classes of graphs
• Progressive algorithms for domination and independence
• Operator-free sparse domination
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Dominating set is fixed parameter tractable in claw-free graphs

This page was built for publication: FPT algorithms for domination in sparse graphs and beyond

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