The bottleneck independent domination on the classes of bipartite graphs and block graphs.

DOI10.1016/S0020-0255(03)00182-8zbMath1050.05100OpenAlexW2064221127MaRDI QIDQ1429835

William Chung-Kung Yen

Publication date: 27 May 2004

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0255(03)00182-8

zbMATH Keywords

NP-hardTreeBlock graphBottleneck costChordal-bipartite graphConvex-bipartite graphIndependent dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Independent rainbow domination of graphs ⋮ On the \(k\)-tuple domination of generalized de Brujin and Kautz digraphs ⋮ On rainbow domination numbers of graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Power domination in block graphs ⋮ \(k\)-power domination in block graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the minimum independent dominating set
• Domination, independent domination, and duality in strongly chordal graphs
• The weighted perfect domination problem
• Finding a maximum independent set in a permutation graph
• Domination in convex and chordal bipartite graphs
• Total domination in interval graphs revisited
• Total domination in block graphs
• Some inequalities about connected domination number
• Independent domination in chordal graphs
• R-domination of block graphs
• Optimum domination in weighted trees
• Single step searching in weighted block graphs
• A Characterization of Block-Graphs
• Planar Formulae and Their Uses
• Scheduling to Minimize Interaction Cost
• Total domination in interval graphs
• Total domination in interval graphs