Approximation hardness of domination problems on generalized convex graphs

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

Unnamed Item
Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
Graph classes with structured neighborhoods and algorithmic applications
Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
Feedback vertex sets on restricted bipartite graphs
Approximating the minimum maximal independence number
On approximating the minimum independent dominating set
Domination, independent domination, and duality in strongly chordal graphs
Domination in convex and chordal bipartite graphs
Approximation hardness of dominating set problems in bounded degree graphs
Labelling algorithms for paired-domination problems in block and interval graphs
The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
Preface: 13th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2015)
Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
HAMILTONian circuits in chordal bipartite graphs
Tractable connected domination for restricted bipartite graphs
A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
Independent Domination on Tree Convex Bipartite Graphs
A threshold of ln n for approximating set cover
Feedback Vertex Sets on Tree Convex Bipartite Graphs
Complexity of Finding Embeddings in a k-Tree
Node-Deletion Problems on Bipartite Graphs
Treewidth of Chordal Bipartite Graphs
Reducibility among Combinatorial Problems
More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
Analytical approach to parallel repetition
Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
Maximum matching in a convex bipartite graph
Solving problems on generalized convex graphs via mim-width

This page was built for publication: Approximation hardness of domination problems on generalized convex graphs