An optimal algorithm to find centres and diameter of a circular-arc graph

MaRDI QIDQ3539510zbMATH OpenFDO

Authors Swagata Mandal, Anita Pal, Madhumangal Pal

Publication date 18 November 2008

Full work available at URL http://www.ici.ro/camo/journal/v9n1.htm

zbMATH Keywords

centrecircular-arc graphdesign and analysis of algorithmsdiameterradius

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Efficient algorithms for centers and medians in interval and circular-arc graphs
• A simple linear-time algorithm for computing the center of an interval graph
• scientific article; zbMATH DE number 1670650
• Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph

Cited in

(7)

• Disconnected cuts in claw-free graphs
• A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
• scientific article; zbMATH DE number 1670650 (Why is no real title available?)
• A simple linear-time algorithm for computing the center of an interval graph
• A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph
• Efficient algorithms for centers and medians in interval and circular-arc graphs
• L(2,1)-labeling of interval graphs

This page was built for publication: An optimal algorithm to find centres and diameter of a circular-arc graph

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