Fixed-Parameter Tractability for Non-Crossing Spanning Trees
DOI10.1007/978-3-540-73951-7_36zbMATH Open1209.68278OpenAlexW1599785870MaRDI QIDQ3603545FDOQ3603545
Christian Knauer, Takeshi Tokuyama, Magnús M. Halldórsson, Andreas Spillner
Publication date: 17 February 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73951-7_36
Recommendations
- Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
- Fixed-parameter tractability results for full-degree spanning tree and its dual
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- Fixed-parameter tractability of treewidth and pathwidth
- Parameterized algorithms for non-separating trees and branchings in digraphs
- An improved lower bound on the maximum number of non-crossing spanning trees
- scientific article; zbMATH DE number 7768369
- Parameterized complexity of the spanning tree congestion problem
- NP-completeness and degree restricted spanning trees
- Fixed-parameter tractability for the tree assembly problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cited In (6)
- Connecting the dots (with minimum crossings)
- Parameterized algorithms for non-separating trees and branchings in digraphs
- Parameterized analysis and crossing minimization problems
- Algorithms and Computation
- Grid recognition: classical and parameterized computational perspectives
- Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
This page was built for publication: Fixed-Parameter Tractability for Non-Crossing Spanning Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603545)
