Hardness results of connected power domination for bipartite graphs and chordal graphs

DOI10.1142/S0129054123410071MaRDI QIDQ6610089zbMATH OpenFDO

Authors Pooja Goyal, B. S. Panda

Publication date 24 September 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054123410071

zbMATH Keywords

connected power dominationdominationgraph algorithmNP-completepolynomial-time algorithm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Connected power domination in graphs
• Generalized power domination of graphs
• Improved algorithms and complexity results for power domination in graphs
• Fundamentals of Computation Theory
• Domination in Graphs Applied to Electric Power Networks

Cites work

• A review of tree convex sets test
• Algorithms and Computation
• Analytical approach to parallel repetition
• Bandwidth of chain graphs
• Computing and Combinatorics
• Connected power domination in graphs
• Domination in Graphs Applied to Electric Power Networks
• Domination in some subclasses of bipartite graphs
• Hardness results of connected power domination for bipartite graphs and chordal graphs
• scientific article; zbMATH DE number 3702724 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Improved algorithms and complexity results for power domination in graphs
• Incidence matrices and interval graphs
• Node-and edge-deletion NP-complete problems
• Parameterized power domination complexity
• Reducibility among combinatorial problems
• Solving the connected dominating set problem and power dominating set problem by integer programming
• Some APX-completeness results for cubic graphs
• Threshold graphs and related topics

This page was built for publication: Hardness results of connected power domination for bipartite graphs and chordal graphs

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