Automata, Languages and Programming

DOI10.1007/b99859zbMath1099.68077OpenAlexW2505584480MaRDI QIDQ5466496

Fedor V. Fomin, Dimitrios M. Thilikos

Publication date: 24 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b99859

zbMATH Keywords

dominating setparameterized algorithmsbranch-widthsubexponential algorithms\(\Sigma\)-embedded graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

Genus characterizes the complexity of certain graph problems: Some tight results ⋮ Parameters estimation in Ebola virus transmission dynamics model based on machine learning ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Approximation algorithms via contraction decomposition ⋮ Subexponential parameterized algorithms ⋮ Branchwidth of chordal graphs ⋮ Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm ⋮ The parameterized complexity of the induced matching problem ⋮ On problems without polynomial kernels ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor ⋮ Dynamic programming for graphs on surfaces ⋮ Twin-width and polynomial kernels

This page was built for publication: Automata, Languages and Programming