Parity graphs form a superclass of bipartite and distance-hereditary graphs. Since their introduc- tion, all the algorithms proposed as solutions to the recognition problem and other combinatorial problems exploit the structural property of these graphs described by Burlet and Uhry (Berge and Chvatal (Eds.), Topics on Perfect Graphs, Ann. Discrete Math., vol. 21, North-Holland, Amsterdam, 1984, pp. 253–277). This paper introduces a dierent structural property of parity graphs: split decomposition returns exactly, as building blocks of parity graphs, cliques and bi- partite graphs. This characterization, together with the observation that the split decomposition process can be performed in linear time, allows us to provide optimum algorithms for both the recognition problem and the maximum weighted clique. Moreover, it can also be used to show that the maximum weighted independent set problem can be solved by an algorithm whose worst complexity occurs when the parity graph considered is bipartite. A remarkable consequence of this work is that the extension of bipartite graphs to parity graphs does not increase the com- plexity of the basic problems we have considered, since the worst case occurs when the parity graph under consideration is an undecomposable bipartite graph.

On the Extension of Bipartite to Parity Graphs

CICERONE, SERAFINO;DI STEFANO, GABRIELE
1999-01-01

Abstract

Parity graphs form a superclass of bipartite and distance-hereditary graphs. Since their introduc- tion, all the algorithms proposed as solutions to the recognition problem and other combinatorial problems exploit the structural property of these graphs described by Burlet and Uhry (Berge and Chvatal (Eds.), Topics on Perfect Graphs, Ann. Discrete Math., vol. 21, North-Holland, Amsterdam, 1984, pp. 253–277). This paper introduces a dierent structural property of parity graphs: split decomposition returns exactly, as building blocks of parity graphs, cliques and bi- partite graphs. This characterization, together with the observation that the split decomposition process can be performed in linear time, allows us to provide optimum algorithms for both the recognition problem and the maximum weighted clique. Moreover, it can also be used to show that the maximum weighted independent set problem can be solved by an algorithm whose worst complexity occurs when the parity graph considered is bipartite. A remarkable consequence of this work is that the extension of bipartite graphs to parity graphs does not increase the com- plexity of the basic problems we have considered, since the worst case occurs when the parity graph under consideration is an undecomposable bipartite graph.
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/11697/21857
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 15
social impact