Finding a shortest non-zero path in group-labeled graphs via permanent computation

DOI10.1007/s00453-016-0142-yzbMath1360.05142OpenAlexW2295069807MaRDI QIDQ524371

Yusuke Kobayashi, Sho Toyooka

Publication date: 2 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://tsukuba.repo.nii.ac.jp/record/41102/files/Algorithmica_77-4.pdf

zbMATH Keywords

permanentgroup-labeled graphsnon-zero shortest path

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (max. 100)

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

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• The complexity of computing the permanent
• Biased graphs. I: Bias, balance, and gains
• Matching is as easy as matrix inversion
• Weakly bipartite graphs and the max-cut problem
• Generating all graph coverings by permutation voltage assignments
• An algebraic matching algorithm
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On a routing problem
• The even-path problem for graphs and digraphs
• Shortest Two Disjoint Paths in Polynomial Time
• The Factorization of Linear Graphs

This page was built for publication: Finding a shortest non-zero path in group-labeled graphs via permanent computation