Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity

DOI10.1137/130949877zbMath1332.05033OpenAlexW2301915442MaRDI QIDQ2797090

Yutaro Yamaguchi

Publication date: 4 April 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/130949877

zbMATH Keywords

disjoint paths\(A\)-pathlinear matroid paritygroup-labelled graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Projective representations and multipliers (20C25)

Related Items

Packing non-zero \(A\)-paths via matroid matching, Finding a path with two labels forbidden in group-labeled graphs, A Weighted Linear Matroid Parity Algorithm, Disjoint non-balanced \(A\)-paths in biased graphs, Half-integrality, LP-branching, and FPT Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Packing non-zero \(A\)-paths via matroid matching
• Packing non-zero \(A\)-paths in group-labelled graphs
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• An augmenting path algorithm for linear matroid parity
• Matroid matching and some applications
• Über die Maximalzahl kreuzungsfreier H-Wege
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Packing non-returning A-paths
• Packing non-returning \(A\)-paths algorithmically
• Algebraic Algorithms for Linear Matroid Parity Problems
• Powers of tensors and fast matrix multiplication
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen