scientific article; zbMATH DE number 7204413

DOI10.4230/LIPICS.MFCS.2017.79zbMATH Open1441.68194arXiv1705.06796MaRDI QIDQ5111296FDOQ5111296

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

Publication date: 26 May 2020

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

Title of this publication is not available (Why is that?)

Recommendations

• scientific article
• 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

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)

Cites Work

• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Easy problems for tree-decomposable graphs
• Minimum-weight triangulation is NP-hard
• The complexity of satisfiability problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Deciding First-Order Properties of Nowhere Dense Graphs
• A Fast Parametric Maximum Flow Algorithm and Applications
• Sparsity. Graphs, structures, and algorithms
• Kernelization Using Structural Parameters on Sparse Graph Classes
• Strong computational lower bounds via parameterized complexity
• Subexponential parameterized algorithms
• Kernelization and Sparseness: the case of Dominating Set
• Contraction and Treewidth Lower Bounds
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Title not available (Why is that?)

Cited In (2)

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

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)