Complexity of approximating the oriented diameter of chordal graphs

DOI10.1002/jgt.10160zbMath1050.05114OpenAlexW4230656706MaRDI QIDQ4459604

Martin Matamala, Ivan Rapaport, Fedor V. Fomin

Publication date: 29 March 2004

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/174969

zbMATH Keywords

algorithmschordal graphsoriented diameter

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter ⋮ Improved bound on the oriented diameter of graphs with given minimum degree ⋮ On the Most Imbalanced Orientation of a Graph ⋮ Improved bounds for the oriented radius of mixed multigraphs ⋮ The complexity of two graph orientation problems ⋮ Series-parallel orientations preserving the cycle-radius ⋮ The oriented diameter of graphs with given connected domination number and distance domination number ⋮ Large girth and small oriented diameter graphs ⋮ A degree condition for diameter two orientability of graphs ⋮ An improvement to Chvátal and Thomassen's upper bound for oriented diameter ⋮ Oriented diameter of star graphs ⋮ Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree ⋮ On the most imbalanced orientation of a graph ⋮ Directing Road Networks by Listing Strong Orientations ⋮ GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE ⋮ Diameter of orientations of graphs with given minimum degree

Cites Work

• Incidence matrices and interval graphs
• Graph Classes: A Survey
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of approximating the oriented diameter of chordal graphs