Parameterized complexity of (A,)-path packing

DOI10.1007/S00453-021-00875-YOpenAlexW4206328452MaRDI QIDQ2118381FDOQ2118381

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)

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the Complexity of General Graph Factor Problems
• 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
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• Easy problems for tree-decomposable graphs
• Color-coding
• Hamilton Paths in Grid Graphs
• Parameterized algorithms
• The complexity of theorem-proving procedures
• Packing non-zero \(A\)-paths in group-labelled graphs
• Treewidth. Computations and approximations
• Sparsity. Graphs, structures, and algorithms
• On the parameterized complexity of multiple-interval graph problems
• The vertex separation and search number of a graph
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The path partition problem and related problems in bipartite graphs
• Über die Maximalzahl kreuzungsfreier H-Wege
• Packing non-returning A-paths
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• Interval graphs and searching
• The complexity of induced minors and related problems
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• Paths in interval graphs and circular arc graphs
• Packing non-returning \(A\)-paths algorithmically
• A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
• A \(c^k n\) 5-approximation algorithm for treewidth
• The disjoint shortest paths problem
• Planar Crossovers
• On the \(k\)-path partition of graphs.
• \(k\)-path partitions in trees

Cited In (5)

• Grundy Distinguishes Treewidth from Pathwidth
• Shortest \((A+B)\)-path packing via hafnian
• Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
• Parameterizing path partitions
• Grouped domination parameterized by vertex cover, twin cover, and beyond

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)