scientific article; zbMATH DE number 7204413

DOI10.4230/LIPICS.MFCS.2017.79MaRDI QIDQ5111296zbMATH OpenFDO

Authors Irene Muzi, Michael P. O'Brien, Felix Reidl, Blair D. Sullivan

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1705.06796

zbMATH Keywords

treewidthNP-completenessETHtopological minorsFPT-algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• scientific article; zbMATH DE number 5917641
• Deep and shallow thinking in the long run
• Pointlessness is better than listlessness
• Ashamed to be selfish
• More triviality
• What Simplicity Is Not
• Hard life with weak binders

Cites work

• A Fast Parametric Maximum Flow Algorithm and Applications
• Contraction and Treewidth Lower Bounds
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Easy problems for tree-decomposable graphs
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization using structural parameters on sparse graph classes
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Minimum-weight triangulation is NP-hard
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Sparsity. Graphs, structures, and algorithms
• Strong computational lower bounds via parameterized complexity
• Subexponential parameterized algorithms
• The complexity of satisfiability problems

Cited in

(2)

• Structural parameterization for minimum conflict-free colouring
• Characterising graphs with no subdivision of a wheel of bounded diameter

This page was built for publication:

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