Circular Convex Bipartite Graphs: Feedback Vertex Set

DOI10.1007/978-3-319-03780-6_24zbMath1339.05399OpenAlexW2400813080MaRDI QIDQ2867126

Ke Xu, Zhao Lu, Min Lu, Tian Liu

Publication date: 10 December 2013

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03780-6_24

zbMATH Keywords

tractabilityfeedback vertex setcircular convex bipartite graphconvex bipartite graphCook reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Tractable connected domination for restricted bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feedback vertex sets on restricted bipartite graphs
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Domination in convex and chordal bipartite graphs
• Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Feedback vertex sets in star graphs
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• 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
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• Node-Deletion Problems on Bipartite Graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Graph Classes: A Survey
• A REVIEW OF TREE CONVEX SETS TEST
• Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract)
• Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
• Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
• Maximum matching in a convex bipartite graph

This page was built for publication: Circular Convex Bipartite Graphs: Feedback Vertex Set