Feedback vertex sets on restricted bipartite graphs

DOI10.1016/j.tcs.2012.12.021zbMath1302.05191OpenAlexW1991742112MaRDI QIDQ393042

Chaoyi Wang, Tian Liu, Wei Jiang, Ke Xu

Publication date: 16 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.021

zbMATH Keywords

NP-completepolynomial timefeedback vertex settree convex bipartite

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Solving problems on generalized convex graphs via mim-width ⋮ Counting independent sets and maximal independent sets in some subclasses of bipartite graphs ⋮ Domination in some subclasses of bipartite graphs ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Counting dominating sets in some subclasses of bipartite graphs ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ Counting independent sets in tree convex bipartite graphs ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ Tractable connected domination for restricted bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Feedback vertex set in hypercubes
• Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
• Hypergraphs with no special cycles
• Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies
• Improved algorithms for feedback vertex set problems
• Improved approximation algorithm for the feedback set problem in a bipartite tournament
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Minimum weight feedback vertex sets in circle graphs
• An efficient algorithm for minimum feedback vertex sets in rotator graphs
• Minimum feedback vertex sets in shuffle-based interconnection networks
• Feedback vertex sets in star graphs
• A characterization of totally balanced hypergraphs
• Almost exact minimum feedback vertex set in meshes and butterflies
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Independent Domination on Tree Convex Bipartite Graphs
• Two Hardness Results on Feedback Vertex Sets
• Finding Induced Subgraphs via Minimal Triangulations
• Feedback Vertex Sets on Tree Convex Bipartite Graphs
• On Feedback Vertex Set New Measure and New Structures
• Feedback Vertex Sets in Rotator Graphs
• A Graph Theoretic Approach to Statistical Data Security
• Node-Deletion Problems on Bipartite Graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Graph Classes: A Survey
• A REVIEW OF TREE CONVEX SETS TEST
• Reducibility among Combinatorial Problems
• Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
• Maximum matching in a convex bipartite graph
• A Min-Max Theorem on Feedback Vertex Sets