Parameterized complexity of \((A,\ell)\)-path packing

DOI10.1007/s00453-021-00875-yOpenAlexW4206328452MaRDI QIDQ2118381

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

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

treewidthfixed-parameter tractability\(A\)-path packing

Mathematics Subject Classification ID

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

Related Items (2)

Grundy Distinguishes Treewidth from Pathwidth ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond

Cites Work

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

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