2019/01/03 by R. Dharmarajan, Dharmarajan, R., D. Ramachandran +1
Computer Science · #05C69 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1901.00626
openalex publication_date 2019/01/03 · openalex created_date 2019/01/11 · openalex updated_date 2026/07/28
In any attempt at designing an efficient algorithm for the minimum vertex cover problem, obtaining good upper and lower bounds for the vertex cover number could be crucial. In this article we present a modified greedy algorithm of worst-case time complexity O(n3) to obtain bounds for the vertex cover number of an input graph of order n. Using simple facts, the proposed algorithm computes a lower bound for the vertex cover number. Then using this lower bound it outputs a minimal vertex cover and hence gives an upper bound. The algorithm ensures the output vertex cover is always minimal, which feature is an improvement upon the existing greedy algorithms.