Tree Convex Bipartite Graphs: \mathcal{NP} -Complete Domination, Hamiltonicity and Treewidth

DOI10.1007/978-3-319-08016-1_23MaRDI QIDQ3188853zbMATH OpenOpenAlexFDO

Authors Chaoyi Wang, Hao Chen, Zihan Lei, Ziyang Tang, Tian Liu, Ke Xu

Publication date 2 September 2014

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-08016-1_23

zbMATH Keywords

treewidthdominationNP-completeHamiltonicitytree convex bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Independent domination on tree convex bipartite graphs
• Bisection of bounded treewidth graphs by convolutions
• Bisection of bounded treewidth graphs by convolutions
• \(R\)-total domination on convex bipartite graphs
• Constrained domatic bipartition on trees
• Hamiltonicity in \(k\)-tree-Halin graphs

Cited in

(13)

• Solving problems on generalized convex graphs via mim-width
• Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Maximum Edge Bicliques in Tree Convex Bipartite Graphs
• Constrained domatic bipartition on trees
• 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
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Independent domination on tree convex bipartite graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Union closed tree convex sets
• Tractable connected domination for restricted bipartite graphs

This page was built for publication: Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188853)