Learn to solve dominating set problem with GNN and reinforcement learning

DOI10.1016/j.amc.2024.128717MaRDI QIDQ6585558zbMATH OpenFDO

Authors Mujia Chen, Sihao Liu, Weihua He

Publication date 12 August 2024

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2024.128717

zbMATH Keywords

combinatorial optimizationdominating set problemgraph neural networkreinforcement learning

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Artificial neural networks and deep learning (68T07) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• A differentiable approach to the maximum independent set problem using dataless neural networks
• NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
• Learning the travelling salesperson problem requires rethinking generalization
• Solving the traveling salesperson problem with precedence constraints by deep reinforcement learning
• scientific article; zbMATH DE number 4201664

Cites work

• ``Neural computation of decisions in optimization problems
• An upper bound for thek-domination number of a graph
• Computing the domination number of grid graphs
• Graph theory with applications
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• Learning heuristics for the TSP by policy gradient
• Models of domination in graphs
• Paradigms of combinatorial optimization. Problems and new approaches
• Statistical mechanics of complex networks
• The domination number of grids

Cited in

(3)

• A differentiable approach to the maximum independent set problem using dataless neural networks
• NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
• A unified pre-training and adaptation framework for combinatorial optimization on graphs

This page was built for publication: Learn to solve dominating set problem with GNN and reinforcement learning

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