Agent Arrangement Problem

arXiv1212.2306MaRDI QIDQ6237909FDOQ6237909

Publication date: 11 December 2012

Abstract: An {em arrangement} of an ordered pair

(G_{A}, G_{M})

of graphs is defined as a function

f

from

V (G_{A})

to

V (G_{M})

such that, for each vertex

c

of

G_{M}

, the vertex-set

f^{- 1} (c)

of

G_{A}

either is

e m p t y s e t

(the case when

c o t i n f (V (G_{A}))

) or induces a connected subgraph of

G_{A}

and that the family

f^{- 1} (y) : y i n V (G_{M}), f^{- 1} (y) e q e m p t y s e t

is a partition of

V (G_{A})

. Let

f

be an arrangement of

(G_{A}, G_{M})

, let

p q

be an edge of

G_{M}

and let

U

be a subset of

f^{- 1} (p)

such that each of the three graphs

G_{A} [U]

,

G_{A} [f^{- 1} (p) s e t m i n u s U]

and

G_{A} [f^{- 1} (q) c u p U]

is ether connected or

e m p t y s e t

and that

. A {em transfer} of

U

from

p

to

q

is defined as the modification

f^{p r i m e}

of

f

such that

f^{p r i m e} (x) := f (x)

for every

x o t i n U

and

f^{p r i m e} (u) := q

for every

u i n U

. Two arrangements

f

and

g

of

(G_{A}, G_{M})

are called {em t-equivalent} if they can be transformed into each other by a finite sequence of transfers. An ordered pair

(G_{A}, G_{M})

of graphs is called {em almighty} if every two arrangements of the pair

(G_{A}, G_{M})

are t-equivalent. In this study, we consider the following two decision problems. [{�f (P1)}]{For a given pair of arrangements

f

and

g

of a given ordered pair

(G_{A}, G_{M})

of graphs, decide whether

f

is t-equivalent to

g

or not.} [{�f (P2)}]{For a given ordered pair

(G_{A}, G_{M})

of graphs, decide whether the pair

(G_{A}, G_{M})

is almighty or not.} We show an

O d (| E (G_{A}) | + (| V (G_{M}) | + | E (G_{A}) |) | V (G_{A}) |)

-time algorithm for {�f (P1)}, and prove the

c o p

-completeness of {�f (P2)}.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57) Boundary value problems on graphs and networks for ordinary differential equations (34B45) Applications of graph theory to circuits and networks (94C15)

This page was built for publication: Agent Arrangement Problem

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