  DCOP algorithms usually rely on interaction graphs to operate. In open and
dynamic environments, such methods need to address how this interaction graph
is generated and maintained among agents. Existing methods require
reconstructing the entire graph upon detecting changes in the environment or
assuming that new agents know potential neighbors to facilitate connection. We
propose a novel distributed interaction graph construction algorithm to address
this problem. The proposed method does not assume a predefined constraint graph
and stabilizes after disruptive changes in the environment. We evaluate our
approach by pairing it with existing DCOP algorithms to solve several generated
dynamic problems. The experiment results show that the proposed algorithm
effectively constructs and maintains a stable multi-agent interaction graph for
open and dynamic environments.
