Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
From MaRDI portal
Publication:328696
DOI10.1007/s10878-015-9917-3zbMath1348.05150OpenAlexW2252286593MaRDI QIDQ328696
Chaoyi Wang, Ke Xu, Tian Liu, Ziyang Tang, Zihan Lei, Hao Chen
Publication date: 20 October 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-015-9917-3
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)
Related Items (12)
Solving problems on generalized convex graphs via mim-width ⋮ Counting independent sets and maximal independent sets in some subclasses of bipartite graphs ⋮ Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy ⋮ Counting dominating sets in some subclasses of bipartite graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ Short cycles dictate dichotomy status of the Steiner tree problem on bisplit 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 ⋮ Dominating induced matching in some subclasses of bipartite graphs
Cites Work
- Unnamed Item
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- Feedback vertex sets on restricted bipartite graphs
- Linear-time algorithm for the paired-domination problem in convex bipartite graphs
- On approximating the minimum independent dominating set
- Domination in convex and chordal bipartite 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
- Treewidth. Computations and approximations
- Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
- Algorithmic graph theory and perfect graphs
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- HAMILTONian circuits in chordal bipartite graphs
- Tractable connected domination for restricted bipartite graphs
- Independent Domination on Tree Convex Bipartite Graphs
- Two Hardness Results on Feedback Vertex Sets
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Union Closed Tree Convex Sets
- Complexity of Finding Embeddings in a k-Tree
- Node-Deletion Problems on Bipartite Graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Graph Classes: A Survey
- Treewidth of Chordal Bipartite Graphs
- Domination in Some Subclasses of Bipartite Graphs
- Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
- Restricted Bipartite Graphs: Comparison and Hardness Results
- Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
- Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems
- Maximum matching in a convex bipartite graph
This page was built for publication: Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
