Minimum weighted clique cover on strip-composed perfect graphs

The only available combinatorial algorithm for the minimum weighted clique cover (mwcc) in claw-free perfect graphs is due to Hsu and Nemhauser [10] and dates back to 1984. More recently, Chudnovsky and Seymour [3] introduced a composition operation, strip-composition, in order to define their struc...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Bonomo, Flavia
Publicado:	2012
Materias:	claw-free graphs minimum weighted clique cover odd pairs of cliques perfect graphs strip-composed graphs Claw-free graphs Clique cover Perfect graph Algorithms Computer science Graphic methods Polynomial approximation Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7551LNCS_n_p22_Bonomo http://hdl.handle.net/20.500.12110/paper_03029743_v7551LNCS_n_p22_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03029743_v7551LNCS_n_p22_Bonomo
record_format	dspace
spelling	paper:paper_03029743_v7551LNCS_n_p22_Bonomo2023-06-08T15:28:49Z Minimum weighted clique cover on strip-composed perfect graphs Bonomo, Flavia claw-free graphs minimum weighted clique cover odd pairs of cliques perfect graphs strip-composed graphs Claw-free graphs Clique cover odd pairs of cliques Perfect graph strip-composed graphs Algorithms Computer science Graphic methods Polynomial approximation Graph theory The only available combinatorial algorithm for the minimum weighted clique cover (mwcc) in claw-free perfect graphs is due to Hsu and Nemhauser [10] and dates back to 1984. More recently, Chudnovsky and Seymour [3] introduced a composition operation, strip-composition, in order to define their structural results for claw-free graphs; however, this composition operation is general and applies to non-claw-free graphs as well. In this paper, we show that a mwcc of a perfect strip-composed graph, with the basic graphs belonging to a class, can be found in polynomial time, provided that the mwcc problem can be solved on in polynomial time. We also design a new, more efficient, combinatorial algorithm for the mwcc problem on strip-composed claw-free perfect graphs. © 2012 Springer-Verlag Berlin Heidelberg. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2012 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7551LNCS_n_p22_Bonomo http://hdl.handle.net/20.500.12110/paper_03029743_v7551LNCS_n_p22_Bonomo
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	claw-free graphs minimum weighted clique cover odd pairs of cliques perfect graphs strip-composed graphs Claw-free graphs Clique cover odd pairs of cliques Perfect graph strip-composed graphs Algorithms Computer science Graphic methods Polynomial approximation Graph theory
spellingShingle	claw-free graphs minimum weighted clique cover odd pairs of cliques perfect graphs strip-composed graphs Claw-free graphs Clique cover odd pairs of cliques Perfect graph strip-composed graphs Algorithms Computer science Graphic methods Polynomial approximation Graph theory Bonomo, Flavia Minimum weighted clique cover on strip-composed perfect graphs
topic_facet	claw-free graphs minimum weighted clique cover odd pairs of cliques perfect graphs strip-composed graphs Claw-free graphs Clique cover odd pairs of cliques Perfect graph strip-composed graphs Algorithms Computer science Graphic methods Polynomial approximation Graph theory
description	The only available combinatorial algorithm for the minimum weighted clique cover (mwcc) in claw-free perfect graphs is due to Hsu and Nemhauser [10] and dates back to 1984. More recently, Chudnovsky and Seymour [3] introduced a composition operation, strip-composition, in order to define their structural results for claw-free graphs; however, this composition operation is general and applies to non-claw-free graphs as well. In this paper, we show that a mwcc of a perfect strip-composed graph, with the basic graphs belonging to a class, can be found in polynomial time, provided that the mwcc problem can be solved on in polynomial time. We also design a new, more efficient, combinatorial algorithm for the mwcc problem on strip-composed claw-free perfect graphs. © 2012 Springer-Verlag Berlin Heidelberg.
author	Bonomo, Flavia
author_facet	Bonomo, Flavia
author_sort	Bonomo, Flavia
title	Minimum weighted clique cover on strip-composed perfect graphs
title_short	Minimum weighted clique cover on strip-composed perfect graphs
title_full	Minimum weighted clique cover on strip-composed perfect graphs
title_fullStr	Minimum weighted clique cover on strip-composed perfect graphs
title_full_unstemmed	Minimum weighted clique cover on strip-composed perfect graphs
title_sort	minimum weighted clique cover on strip-composed perfect graphs
publishDate	2012
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7551LNCS_n_p22_Bonomo http://hdl.handle.net/20.500.12110/paper_03029743_v7551LNCS_n_p22_Bonomo
work_keys_str_mv	AT bonomoflavia minimumweightedcliquecoveronstripcomposedperfectgraphs
_version_	1768543368252489728

Minimum weighted clique cover on strip-composed perfect graphs

Ejemplares similares