Complexity of approximating the oriented diameter of chordal graphs

DOI10.1002/JGT.10160MaRDI QIDQ4459604zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Martin Matamala, Ivan Rapaport

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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1953095
• The complexity of deciding whether a graph admits an orientation with fixed weak diameter
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Approximating the diameter of planar graphs in near linear time
• On the pathwidth of chordal graphs
• Diameters of iterated clique graphs of chordal graphs
• On the proper orientation number of chordal graphs
• scientific article; zbMATH DE number 3991530
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems

Cites work

• Graph Classes: A Survey
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1304325 (Why is no real title available?)
• Incidence matrices and interval graphs

Cited in

(26)

• A degree condition for diameter two orientability of graphs
• AT-free graphs: Linear bounds for the oriented diameter
• An improvement to Chvátal and Thomassen's upper bound for oriented diameter
• Diameter of orientations of graphs with given minimum degree
• A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
• scientific article; zbMATH DE number 1594510 (Why is no real title available?)
• The complexity of deciding whether a graph admits an orientation with fixed weak diameter
• Directing Road Networks by Listing Strong Orientations
• Minimizing the oriented diameter of a planar graph
• 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
• The complexity of two graph orientation problems
• Series-parallel orientations preserving the cycle-radius
• scientific article; zbMATH DE number 1953095 (Why is no real title available?)
• An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Improved bounds for the oriented radius of mixed multigraphs
• The oriented diameter of graphs with given connected domination number and distance domination number
• Large girth and small oriented diameter graphs
• On oriented diameter of (n, k)-star graphs
• On oriented diameter of power graphs
• The oriented diameter of graphs derived from other graphs
• On the oriented diameter of near planar triangulations
• On the most imbalanced orientation of a graph
• Oriented diameter and radius of triangulations

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

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