Title: Computing Minimum Geodetic Sets of Proper Interval Graphs
Abstract: We show that the geodetic number of proper interval graphs can be computed in polynomial time. This problem is $\mbox{\rm NP}$ -hard on chordal graphs and on bipartite weakly chordal graphs. Only an upper bound on the geodetic number of proper interval graphs has been known prior to our result.
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 26
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot