Strongly connected orientations of mixed multigraphs

DOI10.1002/NET.3230150409MaRDI QIDQ3789374zbMATH OpenOpenAlexFDO

Authors M. R. Garey, Fan Chung, Robert E. Tarjan

Publication date 1985

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230150409

zbMATH Keywords

edge orientationlinear-time algorithmmixed multigraphpolynomial-time algorithmreachabilitystrong connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• Improved bounds for the oriented radius of mixed multigraphs
• Orienting graphs to optimize reachability
• Fast parallel strong orientation of mixed graphs and related augmentation problems
• Connected reorientations of mixed multigraphs
• One-way trail orientations

Cited in

(44)

• On a relation between the domination number and a strongly connected bidirection of an undirected graph
• On the optimal strongly connected orientations of city street graphs. IV: Four east-west avenues or north-south streets
• Algorithms for graphs with small octopus
• On optimal orientations of Cartesian products of graphs. I
• Orientations of digraphs almost preserving diameter
• Methods for solving road network problems with disruptions
• The flow index and strongly connected orientations
• Strongly connected orientations of plane graphs
• AT-free graphs: Linear bounds for the oriented diameter
• On optimal orientations of Cartesian products with a bipartite graph
• An improvement to Chvátal and Thomassen's upper bound for oriented diameter
• Diameter of orientations of graphs with given minimum degree
• The edge-orientation problem and some of its variants on weighted graphs
• On optimal orientation of cycle vertex multiplications
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• Graphs with many strong orientations
• Directing Road Networks by Listing Strong Orientations
• Orienting graphs to optimize reachability
• Approximation algorithms for orienting mixed graphs
• On the most imbalanced orientation of a graph
• Improved bound on the oriented diameter of graphs with given minimum degree
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Connected reorientations of mixed multigraphs
• scientific article; zbMATH DE number 4112622 (Why is no real title available?)
• Approximation algorithms for orienting mixed graphs
• One-way trail orientations
• An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter
• On the Structure of the Strong Orientations of a Graph
• Algorithms and Computation
• A note on orientations of mixed graphs
• Improved bounds for the oriented radius of mixed multigraphs
• 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
• The oriented diameter of a bridgeless graph with given \(P_3\)
• Large girth and small oriented diameter graphs
• A note on improved bounds for the oriented radius of mixed multigraphs
• Diameter two orientability of mixed graphs
• Diameter three orientability of mixed bipartite graphs
• The oriented diameter of a bridgeless graph with the given path P_k
• On the oriented diameter of near planar triangulations
• On the most imbalanced orientation of a graph
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• The oriented diameter of mixed multigraphs with diameter 2

This page was built for publication: Strongly connected orientations of mixed multigraphs

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