XNLP-hardness of parameterized problems on planar graphs

DOI10.1007/978-3-031-75409-8_8MaRDI QIDQ6988725zbMATH OpenFDO

Authors Hans L. Bodlaender, Krisztina Szilágyi

Publication date 2 May 2025

Full work available at URL https://doi.org/10.1007/978-3-031-75409-8_8

zbMATH Keywords

outerplanarityparameterized complexityplanar graphsXALPXNLP

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• Approximation algorithms for NP-complete problems on planar graphs
• Determining the Smallest k Such That G Is k-Outerplanar
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On a problem of Sidon in additive number theory and on some related problems.
• On space efficiency of algorithms working on structural decompositions of graphs
• On the complexity of problems on tree-structured graphs
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Polynomial-time data reduction for dominating set
• Problems hard for treewidth but easy for stable gonality
• The parameterised complexity of integer multicommodity flow
• Treewidth. Computations and approximations
• XNLP-completeness for parameterized problems on graphs with a linear structure

Cited in

(1)

• Concurrency constrained scheduling with tree-like constraints

This page was built for publication: XNLP-hardness of parameterized problems on planar graphs

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