Tractable connected domination for restricted bipartite graphs

DOI10.1007/s10878-014-9729-xzbMath1319.90075OpenAlexW2075332443MaRDI QIDQ2354310

Ke Xu, Tian Liu, Zhao Lu

Publication date: 10 July 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-014-9729-x

zbMATH Keywords

polynomial-timeconvex bipartite graphconnected dominationcircular-convex bipartite graphtriad-convex bipartite graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (8)

Solving problems on generalized convex graphs via mim-width ⋮ Domination in some subclasses of bipartite graphs ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Traceability of connected domination critical 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
• Unnamed Item
• On the outer-connected domination in graphs
• Feedback vertex sets on restricted bipartite graphs
• Constructing weakly connected dominating set for secure clustering in distributed sensor network
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
• Domination in convex and chordal bipartite graphs
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Circular Convex Bipartite Graphs: Feedback Vertex Set
• Independent Domination on Tree Convex Bipartite Graphs
• Two Hardness Results on Feedback Vertex Sets
• Feedback Vertex Sets on Tree Convex Bipartite Graphs
• Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract)
• 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

This page was built for publication: Tractable connected domination for restricted bipartite graphs