Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
From MaRDI portal
Publication:328696
DOI10.1007/S10878-015-9917-3zbMATH Open1348.05150OpenAlexW2252286593MaRDI QIDQ328696FDOQ328696
Authors: Zihan Lei, Tian Liu, Ziyang Tang, Chaoyi Wang, Ke Xu, 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
Recommendations
- Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
- Independent domination on tree convex bipartite graphs
- Counting independent sets in tree convex bipartite graphs
- Domination in convex and chordal bipartite graphs
- Tractable connected domination for restricted bipartite graphs
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- Algorithmic graph theory and perfect graphs
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Complexity of Finding Embeddings in a k-Tree
- On approximating the minimum independent dominating set
- Treewidth. Computations and approximations
- HAMILTONian circuits in chordal bipartite graphs
- Node-Deletion Problems on Bipartite Graphs
- Domination in convex and chordal bipartite graphs
- Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
- Independent domination on tree convex bipartite graphs
- Two Hardness Results on Feedback Vertex Sets
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Feedback vertex sets on restricted bipartite graphs
- Perfect Elimination and Chordal Bipartite Graphs
- 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
- Linear-time algorithm for the paired-domination problem in convex bipartite graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Tractable connected domination for restricted bipartite graphs
- Union closed tree convex sets
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- Treewidth of Chordal Bipartite Graphs
- Domination in some subclasses of bipartite graphs
- Restricted Bipartite Graphs: Comparison and Hardness Results
- Set cover, set packing and hitting set for tree convex and tree-like set systems
- Labelling algorithms for paired-domination problems in block and interval graphs
Cited In (21)
- Solving problems on generalized convex graphs via mim-width
- Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
- Induced Matching in Some Subclasses of Bipartite Graphs
- On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
- List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
- Maximum Edge Bicliques in Tree Convex Bipartite Graphs
- Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
- Counting independent sets in tree convex bipartite graphs
- Solving problems on generalized convex graphs via mim-width
- Maximum weight induced matching in some subclasses of bipartite graphs
- Some new algorithmic results on co-secure domination in graphs
- A closer look at Hamiltonicity and domination through the lens of diameter and convexity
- Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
- Independent domination on tree convex bipartite graphs
- Counting dominating sets in some subclasses of bipartite graphs
- Dominating induced matching in some subclasses of bipartite graphs
- Approximation hardness of domination problems on generalized convex graphs
- On convexity in split graphs: complexity of Steiner tree and domination
- Impact of diameter and convex ordering for Hamiltonicity and domination
- Tractable connected domination for restricted bipartite graphs
- Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
This page was built for publication: Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q328696)
