Approximating minimum feedback vertex sets in hypergraphs

DOI10.1016/S0304-3975(99)00043-2MaRDI QIDQ1583598zbMATH OpenWikidataFDO

Authors Toshihiro Fujito

Publication date 31 October 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

hypergraphsfeedback vertex set problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On locating minimum feedback vertex sets
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• Approximating minimum feedback sets and multicuts in directed graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• scientific article; zbMATH DE number 1029225
• scientific article; zbMATH DE number 1342121
• Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
• Feedback vertex set on graphs of low cliquewidth
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• Enumerating minimal subset feedback vertex sets

Cites work

• scientific article; zbMATH DE number 1003266 (Why is no real title available?)
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3876618 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 3215864 (Why is no real title available?)
• A primal-dual approach to approximation of node-deletion problems for matroidal properties
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for NP-hard problems.
• Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
• Optimization, approximation, and complexity classes
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• The approximation of maximum subgraph problems
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(10)

• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• On the feedback number of 3-uniform linear extremal hypergraphs
• Algorithms and Computation
• scientific article; zbMATH DE number 5492392 (Why is no real title available?)
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• On the feedback number of 3-uniform hypergraphs
• Two Hardness Results on Feedback Vertex Sets
• New upper bounds on feedback vertex numbers in butterflies
• Approximating minimum feedback sets and multicuts in directed graphs
• Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT

This page was built for publication: Approximating minimum feedback vertex sets in hypergraphs

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