Parameterized complexity of (A,)-path packing

DOI10.1007/S00453-021-00875-YMaRDI QIDQ2118381zbMATH OpenOpenAlexFDO

Authors Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

Publication date 22 March 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-021-00875-y

zbMATH Keywords

\(A\)-path packingfixed-parameter tractabilitytreewidth

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• Parameterized Complexity of $$(A,\ell )$$-Path Packing
• A Parameterized Perspective on Packing Paths of Length Two
• A parameterized perspective on packing paths of length two
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Paths of bounded length and their cuts: parameterized complexity and algorithms

Cites work

• \(k\)-path partitions in trees
• A c^k n 5-approximation algorithm for treewidth
• A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• Color-coding
• Easy problems for tree-decomposable graphs
• Hamilton Paths in Grid Graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Interval graphs and searching
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• On the \(k\)-path partition of graphs.
• On the Complexity of General Graph Factor Problems
• On the parameterized complexity of multiple-interval graph problems
• Packing non-returning \(A\)-paths algorithmically
• Packing non-returning A-paths
• Packing non-zero \(A\)-paths in group-labelled graphs
• Parameterized algorithms
• Paths in interval graphs and circular arc graphs
• Planar Crossovers
• Sparsity. Graphs, structures, and algorithms
• The complexity of induced minors and related problems
• The complexity of theorem-proving procedures
• The disjoint shortest paths problem
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The path partition problem and related problems in bipartite graphs
• The vertex separation and search number of a graph
• Treewidth. Computations and approximations
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(8)

• Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
• Parameterized Complexity of $$(A,\ell )$$-Path Packing
• Grundy Distinguishes Treewidth from Pathwidth
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Parameterizing path partitions
• On the width of complicated JSJ decompositions
• Tractability of packing vertex-disjoint a-paths under length constraints
• Shortest \((A+B)\)-path packing via hafnian

This page was built for publication: Parameterized complexity of \((A,\ell)\)-path packing

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