A weighting of vertices of a graph is admissible if there exists an edge weighting such that the weight of each vertex equals the sum of weights of its incident edges. Given an admissible vertex weighting of a graph, an invariant set is an edge set such that the sum of the weights of its edges is the same for every edge weighting, and a nonempty invariant set is minimal if none of its nonempty proper subsets is an invariant set. It is easily seen that every nonempty invariant set is a disjoint union of minimal invariant sets. A graphical characterisation of minimal invariant sets in a bipartite graph is known both in the case the vertex weights are reals and in the case the vertex weights are nonnegative reals. We shall state a graphical characterisation of minimal invariant sets in an arbitrary vertex-weighted graph. Moreover, we give a linear algorithm to test an invariant set for minimality. Finally, we state a complete axiomatisation of invariant sets and give a polynomial algorithm to find a set of minimal invariant sets that completely characterise the set of all invariant sets. (C) 2006 Elsevier B.V. All rights reserved.

Francesco Mario, M., Mezzini, M., Marina, M. (2006). Minimal invariant sets in a vertex-weighted graph. THEORETICAL COMPUTER SCIENCE, 362(1-3), 140-161 [10.1016/j.tcs.2006.06.005].

Minimal invariant sets in a vertex-weighted graph

MEZZINI, MAURO;
2006

Abstract

A weighting of vertices of a graph is admissible if there exists an edge weighting such that the weight of each vertex equals the sum of weights of its incident edges. Given an admissible vertex weighting of a graph, an invariant set is an edge set such that the sum of the weights of its edges is the same for every edge weighting, and a nonempty invariant set is minimal if none of its nonempty proper subsets is an invariant set. It is easily seen that every nonempty invariant set is a disjoint union of minimal invariant sets. A graphical characterisation of minimal invariant sets in a bipartite graph is known both in the case the vertex weights are reals and in the case the vertex weights are nonnegative reals. We shall state a graphical characterisation of minimal invariant sets in an arbitrary vertex-weighted graph. Moreover, we give a linear algorithm to test an invariant set for minimality. Finally, we state a complete axiomatisation of invariant sets and give a polynomial algorithm to find a set of minimal invariant sets that completely characterise the set of all invariant sets. (C) 2006 Elsevier B.V. All rights reserved.
Francesco Mario, M., Mezzini, M., Marina, M. (2006). Minimal invariant sets in a vertex-weighted graph. THEORETICAL COMPUTER SCIENCE, 362(1-3), 140-161 [10.1016/j.tcs.2006.06.005].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/146888
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact