Feedback vertex sets on restricted bipartite graphs
From MaRDI portal
Publication:393042
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
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
