2026-08-25T18:47:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27154 2026-08-25T13:18:16Z ddc:004 open_access

Efficient Uniform Negative Edge Weights Geis, Lukas Allendorf, Daniel Bläsius, Thomas Leonhardt, Alexander Meyer, Ulrich Penschuck, Manuel Tran, Hung Random Graphs Shortest Path Random Edge Weights Negative Cycles We consider a maximum entropy edge weight model that allows for negative weights. Given a graph G and possible weights W typically consisting of positive and negative values, the model selects edge weights w ∈ W^m uniformly at random from all weights that do not introduce a negative cycle. We propose an MCMC process and show that it converges to the required distribution. We then engineer an implementation of the process using a dynamic version of Johnson’s algorithm in connection with a bidirectional Dijkstra search as well as an innovative resampling method. We empirically study the performance characteristics of these novel sampling algorithms as well as the output produced by the model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lukas Geis and Daniel Allendorf and Thomas Bläsius and Alexander Leonhardt and Ulrich Meyer and Manuel Penschuck and Hung Tran 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.18 urn:nbn:de:0030-drops-271542 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode