Domination in some subclasses of bipartite graphs

DOI10.1016/J.DAM.2018.03.029zbMath1401.05222OpenAlexW4206145016MaRDI QIDQ1630774

Arti Pandey, B. S. Panda

Publication date: 10 December 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.03.029

zbMATH Keywords

NP-completenessdominationgraph classesconvex bipartite graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (12)

Solving problems on generalized convex graphs via mim-width ⋮ Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ Acyclic matching in some subclasses of graphs ⋮ P versus NPC: minimum Steiner trees in convex split graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ Algorithmic and complexity aspects of problems related to total restrained domination for graphs ⋮ Global total \(k\)-domination: approximation and hardness results ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ Differentiating-total domination: approximation and hardness results ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ On the complexity of minimum maximal uniquely restricted matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Circular convex bipartite graphs: feedback vertex sets
• Feedback vertex sets on restricted bipartite graphs
• Dominating sets for split and bipartite graphs
• Domination in convex and chordal bipartite graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Tractable connected domination for restricted bipartite graphs
• Independent Domination on Tree Convex Bipartite Graphs
• A threshold of ln n for approximating set cover
• A REVIEW OF TREE CONVEX SETS TEST
• Reducibility among Combinatorial Problems
• Domination in Some Subclasses of Bipartite Graphs
• Restricted Bipartite Graphs: Comparison and Hardness Results
• Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs

This page was built for publication: Domination in some subclasses of bipartite graphs