Approximation hardness of domination problems on generalized convex graphs
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- Domination in some subclasses of bipartite graphs
- Domination in some subclasses of bipartite graphs
- Counting dominating sets in some subclasses of bipartite graphs
- Independent domination on tree convex bipartite graphs
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
Cites work
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- A threshold of ln n for approximating set cover
- Analytical approach to parallel repetition
- Approximating the minimum maximal independence number
- Approximation hardness of dominating set problems in bounded degree graphs
- Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- Complexity of Finding Embeddings in a k-Tree
- Domination in convex and chordal bipartite graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Feedback vertex sets on restricted bipartite graphs
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Graph classes with structured neighborhoods and algorithmic applications
- HAMILTONian circuits in chordal bipartite graphs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Independent domination on tree convex bipartite graphs
- Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- Maximum matching in a convex bipartite graph
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Node-Deletion Problems on Bipartite Graphs
- On approximating the minimum independent dominating set
- Preface: 13th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2015)
- Reducibility among combinatorial problems
- Solving problems on generalized convex graphs via mim-width
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Tractable connected domination for restricted bipartite graphs
- Treewidth of Chordal Bipartite Graphs
Cited in
(2)
This page was built for publication: Approximation hardness of domination problems on generalized convex graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6664063)
