Parameterized Complexity of $$(A,\ell )$$-Path Packing

DOI10.1007/978-3-030-48966-3_4OpenAlexW3031065515MaRDI QIDQ5041178

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

Publication date: 13 October 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.03448

zbMATH Keywords

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

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
• Über die Maximalzahl kreuzungsfreier H-Wege
• Treewidth. Computations and approximations
• \(k\)-path partitions in trees
• On the \(k\)-path partition of 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
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Color-coding
• Paths, Trees, and Flowers
• Parameterized Algorithms
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth