Shortest \((A+B)\)-path packing via hafnian

DOI10.1007/s00453-017-0334-0zbMath1396.68058arXiv1603.08073OpenAlexW2963286134MaRDI QIDQ724248

Hiroyuki Namba, Hiroshi Hirai

Publication date: 25 July 2018

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

hafnianrandomized polynomial-time algorithmshortest disjoint paths problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Randomized algorithms (68W20)

Related Items (5)

Faster 2-Disjoint-Shortest-Paths Algorithm ⋮ Unnamed Item ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Shortest Two Disjoint Paths in Polynomial Time ⋮ The Directed Disjoint Shortest Paths Problem

Cites Work

• Unnamed Item
• On shortest disjoint paths in planar graphs
• Tree metrics and edge-disjoint \(S\)-paths
• Finding a shortest non-zero path in group-labeled graphs via permanent computation
• The complexity of computing the permanent
• Matching is as easy as matrix inversion
• Disjoint paths in graphs
• 2-linked graphs
• Graph minors. XIII: The disjoint paths problem
• Shortest vertex-disjoint two-face paths in planar graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity
• Shortest Two Disjoint Paths in Polynomial Time
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen

This page was built for publication: Shortest \((A+B)\)-path packing via hafnian