Abstract
For the minimum feedback vertex set problem, we show a linear time algorithm for bipartite permutation graphs, the NP-hardness for grid intersection graphs, and a polynomial time algorithm for graphs with maximum degree at most three.
2012 Third International Conference on Networking and Computing
Like what you’re reading?
Already a member?
Related Articles
- An 8-approximation algorithm for the subset feedback vertex set problem
Proceedings of 37th Conference on Foundations of Computer Science - Computing Minimum Feedback Vertex Sets by Contraction Operations and its Applications on CAD
Proceedings 1999 IEEE International Conference on Computer Design: VLSI in Computers and Processors (Cat. No.99CB37040) - Total k-Domatic Partition on Some Classes of Graphs
2016 International Computer Symposium (ICS) - Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts
2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) - Broadcasting in Weighted-Vertex Graphs
2008 IEEE International Symposium on Parallel and Distributed Processing with Applications - Using expander graphs to find vertex connectivity
Proceedings 41st Annual Symposium on Foundations of Computer Science - The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science - On interval edge-colorings of bipartite graphs
2015 Computer Science and Information Technologies (CSIT) - An Efficient Parallel Recognition Algorithm For Bipartite-Permutation Graphs
IEEE Transactions on Parallel & Distributed Systems - A New Efficient Algorithm for Weighted Vertex Cover in Bipartite Graphs Based on a Dual Problem
2018 9th International Conference on Information Technology in Medicine and Education (ITME)