Directing Road Networks by Listing Strong Orientations

DOI10.1007/978-3-319-44543-4_7zbMath1478.68226OpenAlexW2530640517MaRDI QIDQ2819493

Romeo Rizzi, Andrea Marino, Alessio Conte, Roberto Grossi, Luca Versari

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01388476/file/Strong_Orientations.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (8)

FPT algorithms to enumerate and count acyclic and totally cyclic orientations ⋮ Efficient enumeration of graph orientations with sources ⋮ Model and methods to address urban road network problems with disruptions ⋮ The strong network orientation problem ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ Enumerating \(k\)-arc-connected orientations ⋮ Maximal strongly connected cliques in directed graphs: algorithms and bounds ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Finding strong bridges and strong articulation points in linear time
• On orientations and shortest paths
• Distances in orientations of graphs
• On the optimal strongly connected orientations of city street graphs. IV: Four east-west avenues or north-south streets
• Minimizing and maximizing the diameter in orientations of graphs
• AT-free graphs: Linear bounds for the oriented diameter
• Optimal orientations of graphs and digraphs: A survey
• Minimum average distance of strong orientations of graphs
• Enumerating Cyclic Orientations of a Graph
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• On the Most Imbalanced Orientation of a Graph
• On the sum of all distances in a graph or digraph
• On the optimal strongly connected orientations of city street graphs. II: Two east-west avenues or North—South Streets
• Strongly connected orientations of mixed multigraphs
• On the Optimal Strongly Connected Orientations of City Street Graphs I: Large Grids
• Robbins's Theorem for Mixed Multigraphs
• On the optimal strongly connected orientations of city street graphs. III. Three east–west avenues or north–south streets
• Complexity of approximating the oriented diameter of chordal graphs
• Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
• Bounds for the minimum oriented diameter
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Notes on acyclic orientations and the shelling lemma
• A note on orientations of mixed graphs

This page was built for publication: Directing Road Networks by Listing Strong Orientations