Algorithmic study on liar's vertex-edge domination problem

DOI10.1007/S10878-024-01208-9MaRDI QIDQ6646745zbMATH OpenFDO

Authors Debojyoti Bhattacharya, S. Paul

Publication date 3 December 2024

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

Full work available at URL https://doi.org/10.1007/S10878-024-01208-9

zbMATH Keywords

approximation algorithmsbipartite graphschordal graphsliar's vertex-edge dominating setNP-completeness

Mathematics Subject Classification ID

Trees (05C05) 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

• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Connected liar's domination in graphs: complexity and algorithms
• Liar's domination in graphs: complexity and algorithm
• Hardness results and approximation algorithm for total liar's domination in graphs
• A linear time algorithm for liar's domination problem in proper interval graphs

Cites work

• Double vertex-edge domination
• Double vertex-edge domination in graphs: complexity and algorithms
• Global vertex-edge domination sets in graph
• Global vertex-edge domination sets in total graph and product graph of path \(P_n\) cycle \(C_n\)
• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Introduction to algorithms
• Liar's domination
• Liar's domination in graphs
• Liar's domination in graphs: complexity and algorithm
• Liar's domination in unit disk graphs
• Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
• Polynomial time algorithm for k-vertex-edge dominating problem in interval graphs
• Results on vertex-edge and independent vertex-edge domination
• Total vertex-edge domination
• Total vertex-edge domination in trees
• Vertex-edge domination in graphs
• Vertex-edge domination in graphs
• Vertex-edge domination in unit disk graphs

This page was built for publication: Algorithmic study on liar's vertex-edge domination problem

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