Route-enabling graph orientation problems

DOI10.1007/s00453-011-9589-zzbMath1259.68079OpenAlexW1996360772MaRDI QIDQ1939659

Yuichiro Miyamoto, Ryuhei Uehara, Hirotaka Ono, Hisao Tamaki, Takehiro Ito

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9589-z

zbMATH Keywords

dynamic programmingreachabilityapproximation algorithmplanar graphgraph orientationcactusfully polynomial-time approximation scheme

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orienting graphs to optimize reachability
• Distances in orientations of graphs
• Current trends in deterministic scheduling
• A review of design and control of automated guided vehicle systems
• Minimizing the Oriented Diameter of a Planar Graph
• ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
• Route-Enabling Graph Orientation Problems
• Graph Classes: A Survey
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• A Theorem on Graphs, with an Application to a Problem of Traffic Control

This page was built for publication: Route-enabling graph orientation problems