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

DOI10.1007/978-3-319-08016-1_23zbMath1407.68198OpenAlexW271098353MaRDI QIDQ3188853

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

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

treewidthHamiltonicityNP-completedominationtree 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)

Related Items (5)

Solving problems on generalized convex graphs via mim-width ⋮ Union Closed Tree Convex Sets ⋮ 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

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