Complexity of approximating the oriented diameter of chordal graphs
From MaRDI portal
Publication:4459604
DOI10.1002/JGT.10160zbMATH Open1050.05114OpenAlexW4230656706MaRDI QIDQ4459604FDOQ4459604
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
Cited In (22)
- On oriented diameter of \((n, k)\)-star graphs
- A degree condition for diameter two orientability of graphs
- The complexity of two graph orientation problems
- An improvement to Chvátal and Thomassen's upper bound for oriented diameter
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- Series-parallel orientations preserving the cycle-radius
- On the most imbalanced orientation of a graph
- Improved bounds for the oriented radius of mixed multigraphs
- The oriented diameter of graphs with given connected domination number and distance domination number
- Title not available (Why is that?)
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- Improved bound on the oriented diameter of graphs with given minimum degree
- Large girth and small oriented diameter graphs
- On the Most Imbalanced Orientation of a Graph
- Directing Road Networks by Listing Strong Orientations
- Oriented diameter of star graphs
- An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- The complexity of deciding whether a graph admits an orientation with fixed weak diameter
- AT-free graphs: Linear bounds for the oriented diameter
- Diameter of orientations of graphs with given minimum degree
- Title not available (Why is that?)
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)
