Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Two Hardness Results on Feedback Vertex Sets
verfasst von : Wei Jiang, Tian Liu, Tienan Ren, Ke Xu
Erschienen in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A feedback vertex set is a subset of vertices whose deletion makes the remaining graph a forest. We show that the minimum FVS (MFVS) in star convex bipartite graphs is
$\mathcal{NP}$
-hard to find, and give a tighter lower bound on the size of MFVS in sparse random graphs, to provide further evidence on the hardness of random CSPs.