Single source shortest paths in H-minor free graphs

DOI10.1016/J.TCS.2010.04.028zbMATH Open1196.68177OpenAlexW2147735052MaRDI QIDQ986535FDOQ986535

Authors: Raphael Yuster 

Publication date: 11 August 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.04.028

Recommendations

• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Undirected single-source shortest paths with positive integer weights in linear time
• Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time

zbMATH Keywords

shortest paths\(H\)-minor free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• A note on two problems in connexion with graphs
• Generalized Nested Dissection
• On a routing problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Graph minors. XX: Wagner's conjecture
• Scaling algorithms for network problems
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Faster Scaling Algorithms for Network Problems
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Title not available (Why is that?)
• Graph minor theory
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Kuratowski's theorem
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Faster shortest-path algorithms for planar graphs
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Shortest paths in directed planar graphs with negative lengths
• Title not available (Why is that?)
• Fast separation in a graph with an excluded minor
• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• Title not available (Why is that?)

Cited In (2)

• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• Simple PTAS's for families of graphs excluding a minor

This page was built for publication: Single source shortest paths in \(H\)-minor free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986535)