An algorithm for packing non-zero \(A\)-paths in group-labelled graphs

DOI10.1007/s00493-008-2157-8zbMath1164.05029OpenAlexW2032198109MaRDI QIDQ949790

Maria Chudnovsky, William H. Cunningham, Jim Geelen

Publication date: 21 October 2008

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-008-2157-8

zbMATH Keywords

oriented graph\(A\)-pathweight of a path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (14)

Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ Packing non-zero \(A\)-paths via matroid matching ⋮ Finding a path with two labels forbidden in group-labeled graphs ⋮ Finding Maximum Edge-Disjoint Paths Between Multiple Terminals ⋮ Synchronization problems in computer vision with closed-form solutions ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Packing non-returning \(A\)-paths algorithmically ⋮ A fast algorithm for the path 2-packing problem ⋮ Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Excluding a group-labelled graph ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Packing non-zero \(A\)-paths in group-labelled graphs
• Matroid matching and some applications
• Über die Maximalzahl kreuzungsfreier H-Wege

This page was built for publication: An algorithm for packing non-zero \(A\)-paths in group-labelled graphs