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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2012
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06216caa a22007097a 4500 | ||
|---|---|---|---|
| 001 | PAPER-9194 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203904.0 | ||
| 008 | 190411s2012 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84868022365 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a Minimum weighted clique cover on strip-composed perfect graphs |
| 260 | |c 2012 | ||
| 270 | 1 | 0 | |m Bonomo, F.; IMAS-CONICET and Departamento de Computación, FCEN, Universidad de Buenos AiresArgentina; email: fbonomo@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Burlet, M., Maffray, F., Trotignon, N., Odd pairs of cliques (2007) Proc. of A Conference in Memory of Claude Berge, pp. 85-95. , Birkhäuser | ||
| 504 | |a Chudnovskym, Seymour, P., Claw-free Graphs VII, , Quasi-line graphs. J. Combin. Theory, Ser. B (to appear | ||
| 504 | |a Chudnovsky, M., Seymour, P., The structure of claw-free graphs (2005) London Math. Soc. Lecture Note Ser., 327, pp. 153-171 | ||
| 504 | |a Eisenbrand, F., Oriolo, G., Stauffer, G., Ventura, P., Circular one matrices and the stable set polytope of quasi-line graphs (2008) Combinatorica, 28 (1), pp. 45-67 | ||
| 504 | |a Faenza, Y., Oriolo, G., Stauffer, G., An algorithmic decomposition of claw-free graphs leading to an O(n3)-algorithm for the weighted stable set problem (2011) Proc. 22nd SODA, pp. 630-646. , Randall, D. (ed.) San Francisco CA | ||
| 504 | |a Gabow, H., Data structures for weighted matching and nearest common ancestors with linking (1990) Proc. 1st SODA, pp. 434-443. , San Francisco CA | ||
| 504 | |a Grötschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer, Berlin | ||
| 504 | |a Hermelin, D., Mnich, M., Van Leeuwen, E., Woeginger, G., Domination when the stars are out (2011) ICALP 2011. LNCS, 6755, pp. 462-473. , Aceto, L., Henzinger, M., Sgall, J. (eds.) Springer, Heidelberg | ||
| 504 | |a Hsu, W., Nemhauser, G., Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs (1981) Discrete Math., 37, pp. 181-191 | ||
| 504 | |a Hsu, W., Nemhauser, G., Algorithms for maximum weight cliques, minimum weighted clique covers and cardinality colorings of claw-free perfect graphs (1984) Ann. Discrete Math., 21, pp. 317-329 | ||
| 504 | |a Minty, G., On maximal independent sets of vertices in claw-free graphs (1980) J. Combin. Theory, Ser. B, 28 (3), pp. 284-304 | ||
| 504 | |a Nakamura, D., Tamura, A., A revision of Minty's algorithm for finding a maximum weighted stable set of a claw-free graph (2001) J. Oper. Res. Soc. Japan, 44 (2), pp. 194-204 | ||
| 504 | |a Nobili, P., Sassano, A., A reduction algorithm for the weighted stable set problem in claw-free graphs (2011) Proc. 10th CTW, pp. 223-226. , Frascati Italy | ||
| 504 | |a Oriolo, G., Pietropaoli, U., Stauffer, G., A new algorithm for the maximum weighted stable set problem in claw-free graphs (2008) IPCO 2008. LNCS, 5035, pp. 77-96. , Lodi, A., Panconesi, A., Rinaldi, G. (eds.)Springer, Heidelberg | ||
| 504 | |a Schrijver, A., Combinatorial optimization (2003) Polyhedra and Efficiency(3 Volumes Algorithms and Combinatorics, 24. , Springer Berlin | ||
| 504 | |a Trotter, L., Line perfect graphs (1977) Math. Program., 12, pp. 255-259A4 - University of Haifa; Caesarea Rothschild Inst. Interdiscip. Appl. Comput. Sci.; I-Core - Israeli Center of Excellence in Algorithms; Springer | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a IMAS-CONICET and Departamento de Computación, FCEN, Universidad de Buenos Aires, Argentina | ||
| 593 | |a Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Italy | ||
| 690 | 1 | 0 | |a CLAW-FREE GRAPHS |
| 690 | 1 | 0 | |a MINIMUM WEIGHTED CLIQUE COVER |
| 690 | 1 | 0 | |a ODD PAIRS OF CLIQUES |
| 690 | 1 | 0 | |a PERFECT GRAPHS |
| 690 | 1 | 0 | |a STRIP-COMPOSED GRAPHS |
| 690 | 1 | 0 | |a CLAW-FREE GRAPHS |
| 690 | 1 | 0 | |a CLIQUE COVER |
| 690 | 1 | 0 | |a ODD PAIRS OF CLIQUES |
| 690 | 1 | 0 | |a PERFECT GRAPH |
| 690 | 1 | 0 | |a STRIP-COMPOSED GRAPHS |
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a COMPUTER SCIENCE |
| 690 | 1 | 0 | |a GRAPHIC METHODS |
| 690 | 1 | 0 | |a POLYNOMIAL APPROXIMATION |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 700 | 1 | |a Oriolo, G. | |
| 700 | 1 | |a Snels, C. | |
| 711 | 2 | |c Jerusalem |d 26 June 2012 through 28 June 2012 |g Código de la conferencia: 93608 | |
| 773 | 0 | |d 2012 |g v. 7551 LNCS |h pp. 22-33 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 9783642346101 |t 38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84868022365&doi=10.1007%2f978-3-642-34611-8_6&partnerID=40&md5=4e9efd91b112bbac87412ba5163d8a4e |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/978-3-642-34611-8_6 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v7551LNCS_n_p22_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7551LNCS_n_p22_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v7551LNCS_n_p22_Bonomo |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 70147 | ||