### Complexity of approximating the oriented diameter of chordal graphs

### Abstract

The oriented diameter of a bridgeless connected undirected (bcu) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear-time approximation algorithm that, for a given chordal bcu graph G, finds a strongly connected orientation of G with diameter at most one plus twice the oriented diameter of G; (b) prove that, for every k ? 2 and k ? 3, to decide whether a chordal (split for k = 2) bcu graph G admits an orientation of diameter k is NP-complete; (c) show that, unless P = NP, there is neither a polynomial-time absolute approximate algorithm nor an ?-approximation algorithm that computes the oriented diameter of a bcu chordal graph for ? < 2/3. © 2004 Wiley Periodicals, Inc.

### Más información

Título según WOS: | Complexity of approximating the oriented diameter of chordal graphs |

Título según SCOPUS: | Complexity of approximating the oriented diameter of chordal graphs |

Título de la Revista: | JOURNAL OF GRAPH THEORY |

Volumen: | 45 |

Número: | 4 |

Editorial: | Wiley |

Fecha de publicación: | 2004 |

Página de inicio: | 255 |

Página final: | 269 |

Idioma: | English |

URL: | http://doi.wiley.com/10.1002/jgt.10160 |

DOI: |
10.1002/jgt.10160 |

Notas: | ISI, SCOPUS |