Approximation hardness of domination problems on generalized convex graphs
DOI10.1016/J.TCS.2024.115035MaRDI QIDQ6664063FDOQ6664063
Authors: Po-Yuan Wang, Naoki Kitamura, Taisuke Izumi, Toshimitsu Masuzawa 
Publication date: 16 January 2025
Published in: Theoretical Computer Science (Search for Journal in Brave)
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
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
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Complexity of Finding Embeddings in a k-Tree
- Approximating the minimum maximal independence number
- On approximating the minimum independent dominating set
- HAMILTONian circuits in chordal bipartite graphs
- Node-Deletion Problems on Bipartite Graphs
- Domination in convex and chordal bipartite graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
- Independent domination on tree convex bipartite graphs
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Feedback vertex sets on restricted bipartite graphs
- Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
- Maximum matching in a convex bipartite graph
- Graph classes with structured neighborhoods and algorithmic applications
- Analytical approach to parallel repetition
- 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
- Tractable connected domination for restricted bipartite graphs
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- Treewidth of Chordal Bipartite Graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
- Preface: 13th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2015)
- Solving problems on generalized convex graphs via mim-width
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)
