Premium
Feedback vertex set on cocomparability graphs
Author(s) -
Coorg Satyan R.,
Rangan C. Pandu
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260205
Subject(s) - vertex (graph theory) , combinatorics , computer science , set (abstract data type) , graph , mathematics , programming language
Given an undirected graph, The feedback vertex set problem is to find a set of vertices of minimum cardinality such that removing the vertices in this set makes the graph acyclic. This problem is known to be NP‐hard on general graphs. An O ( n 6 ) algorithm for this problem on permutation graphs is known. in this paper, we give an O ( n 4 ) algorithm for this problem on cocomparability graphs. Our result improves the time complexity of the algorithm and enlarges the class of graphs on which this problem is polynomial time‐solvable.