Complexity of approximating the oriented diameter of chordal graphs

DOI10.1002/JGT.10160MaRDI QIDQ4459604zbMATHOpenAlexFDO

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

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

Cited in

(22)

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

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)