Minimum clique cover in claw-free perfect graphs and the weak Edmonds-Johnson property
We give new algorithms for the minimum (weighted) clique cover in a claw-free perfect graph G, improving the complexity from O(|V(G)|5) to O(|V(G)|3). The new algorithms build upon neat reformulations of the problem: it basically reduces either to solving a 2-SAT instance (in the unweighted case) or...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2013
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 08587caa a22008897a 4500 | ||
|---|---|---|---|
| 001 | PAPER-24304 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518205608.0 | ||
| 008 | 190411s2013 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84875517087 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a Minimum clique cover in claw-free perfect graphs and the weak Edmonds-Johnson property |
| 260 | |c 2013 | ||
| 270 | 1 | 0 | |m Bonomo, F.; IMAS-CONICET, Departamento de Computación, Universidad de Buenos AiresArgentina; email: fbonomo@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Aspvall, B., Plass, M., Tarjan, R., A linear-time algorithm for testing the truth of certain quantified boolean formulas (1979) Inf. Process. Lett., 8 (3), pp. 121-123 | ||
| 504 | |a Bagnara, R., Hill, P.M., Zaffanella, E., An improved tight closure algorithm for integer octagonal constraints (2008) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4905 LNCS, pp. 8-21. , DOI 10.1007/978-3-540-78163-9-6, Verification, Model Checking, and Abstract Interpretation - 9th International Conference, VMCAI 2008, Proceedings | ||
| 504 | |a Berge, C., (1973) Graphs and Hypergraphs, , Dunod, Paris | ||
| 504 | |a Bonomo, F., Oriolo, G., Snels, C., Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs (2012) LNCS, 7551, pp. 22-33. , Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. Springer, Heidelberg | ||
| 504 | |a Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory, 18 (2), pp. 138-154. , Ser. B | ||
| 504 | |a Chvátal, V., Sbihi, N., Recognizing claw-free perfect graphs (1988) J. Combin. Theory, 44, pp. 154-176. , Ser. B | ||
| 504 | |a Edmonds, J., Johnson, E., Matching: A well-solved class of integer linear programs (1970) Combinatorial Structures and Their Applications, pp. 89-92. , Guy, R., Hanani, H., Sauer, N., Schönheim, J. (eds.) Gordon and Breach, New York | ||
| 504 | |a Edmonds, J., Johnson, E., Matching, Euler tours and the Chinese postman (1973) Math. Program., 5, pp. 88-124 | ||
| 504 | |a Faenza, Y., Oriolo, G., Stauffer, G., An algorithmic decomposition of claw-free graphs leading to an O (n 3)-algorithm for the weighted stable set problem (2011) Proc. 22nd SODA, San Francisco, CA, pp. 630-646. , Randall, D. (ed.) | ||
| 504 | |a Fulkerson, D., On the perfect graph theorem (1973) Mathematical Programming, pp. 69-76. , Hu, T., Robinson, S. (eds.) Academic Press, New York | ||
| 504 | |a Gerards, A., Schrijver, A., Matrices with the Edmonds-Johnson property (1986) Combinatorica, 6 (4), pp. 365-379 | ||
| 504 | |a Grötschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer, Berlin | ||
| 504 | |a Harvey, W., Stuckey, P., A unit two variable per inequality integer constraint solver for constraint logic programming (1997) The 20th Australasian Computer Science Conference, Sydney, Australia, pp. 102-111. , Australian Computer Science Communications | ||
| 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., A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs (1982) Discrete Math., 38 (1), pp. 65-71 | ||
| 504 | |a Jaffar, J., Maher, M.J., Stuckey, P.J., Yap, R.H.C., Beyond Finite Domains (1994) LNCS, 874, pp. 86-94. , PPCP 1994. Springer, Heidelberg | ||
| 504 | |a Korte, B., Vygen, J., (2011) Combinatorial Optimization: Theory and Algorithms, , Springer, Berlin | ||
| 504 | |a Lahiri, S.K., Musuvathi, M., An Efficient Decision Procedure for UTVPI Constraints (2005) LNCS (LNAI), 3717, pp. 168-183. , Gramlich, B. (ed.) FroCos 2005. Springer, Heidelberg | ||
| 504 | |a Maffray, F., Reed, B., A description of claw-free perfect graphs (1999) J. Combin. Theory, 75 (1), pp. 134-156. , Ser. B | ||
| 504 | |a Padberg, M., Perfect zero-one matrices (1974) Math. Program., 6, pp. 180-196 | ||
| 504 | |a Peis, B., (2007) Structure Analysis of Some Generalizations of Matchings and Matroids under Algorithmic Aspects, , PhD thesis, Universität zu Köln | ||
| 504 | |a Schrijver, A., Disjoint homotopic paths and trees in a planar graph (1991) Discrete Comput. Geom., 6 (1), pp. 527-574 | ||
| 504 | |a Schrijver, A., Combinatorial Optimization. Polyhedra and Efficiency (2003) Algorithms and Combinatorics, 24. , 3 volumes. Springer, Berlin | ||
| 504 | |a Schutt, A., Stuckey, P., Incremental satisfiability and implication for UTVPI constraints (2010) INFORMS J. Comput., 22 (4), pp. 514-527 | ||
| 504 | |a Seshia, S., Subramani, K., Bryant, R., On solving Boolean combinations of UTVPI constraints (2007) J. Satisf. Boolean Model. Comput., 3, pp. 67-90 | ||
| 504 | |a Tarjan, R., Depth-first search and linear graph algorithms (1972) SIAM J. Comput., 1 (2), pp. 146-160 | ||
| 504 | |a Whitesides, S., A method for solving certain graph recognition and optimization problems, with applications to perfect graphs (1984) North-Holland Mathematics Studies, 88, pp. 281-297. , Berge, C., Chvátal, V. (eds.) Topics on Perfect Graphs, North-HollandA4 - Mathematical Optimization Society | ||
| 520 | 3 | |a We give new algorithms for the minimum (weighted) clique cover in a claw-free perfect graph G, improving the complexity from O(|V(G)|5) to O(|V(G)|3). The new algorithms build upon neat reformulations of the problem: it basically reduces either to solving a 2-SAT instance (in the unweighted case) or to testing if a polyhedra associated with the edge-vertex incidence matrix of a bidirected graph has an integer solution (in the weighted case). The latter question was elegantly answered using neat polyhedral arguments by Schrijver in 1994. We give an alternative approach to this question combining pure combinatorial arguments (using techniques from 2-SAT and shortest paths) with polyhedral ones. Our approach is inspired by an algorithm from the Constraint Logic Programming community and we give as a side benefit a formal proof that the corresponding algorithm is correct (apparently answering an open question in this community). Interestingly, the systems we study have properties closely connected with the so-called Edmonds-Johnson property and we study some interesting related questions. © 2013 Springer-Verlag. |l eng | |
| 593 | |a IMAS-CONICET, Departamento de Computación, Universidad de Buenos Aires, Argentina | ||
| 593 | |a Dipartimento di Ingegneria Civile e Ingegneria Informatica, Università Tor Vergata, Roma, Italy | ||
| 593 | |a Bordeaux Institute of Mathematics, France | ||
| 690 | 1 | 0 | |a BIDIRECTED GRAPHS |
| 690 | 1 | 0 | |a CLAW-FREE PERFECT GRAPHS |
| 690 | 1 | 0 | |a CLIQUE COVER |
| 690 | 1 | 0 | |a EDMONDS-JOHNSON PROPERTY |
| 690 | 1 | 0 | |a ALTERNATIVE APPROACH |
| 690 | 1 | 0 | |a BIDIRECTED GRAPH |
| 690 | 1 | 0 | |a CLIQUE COVER |
| 690 | 1 | 0 | |a CONSTRAINT LOGIC PROGRAMMING |
| 690 | 1 | 0 | |a EDMONDS-JOHNSON PROPERTY |
| 690 | 1 | 0 | |a INCIDENCE MATRICES |
| 690 | 1 | 0 | |a INTEGER SOLUTIONS |
| 690 | 1 | 0 | |a PERFECT GRAPH |
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a COMBINATORIAL OPTIMIZATION |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING |
| 690 | 1 | 0 | |a LOGIC PROGRAMMING |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 700 | 1 | |a Oriolo, G. | |
| 700 | 1 | |a Snels, C. | |
| 700 | 1 | |a Stauffer, G. | |
| 711 | 2 | |c Valparaiso |d 18 March 2013 through 20 March 2013 |g Código de la conferencia: 96207 | |
| 773 | 0 | |d 2013 |g v. 7801 LNCS |h pp. 86-97 |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 9783642366932 |t 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84875517087&doi=10.1007%2f978-3-642-36694-9_8&partnerID=40&md5=35bf67fe14df086fcc4de7358d20c21f |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/978-3-642-36694-9_8 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v7801LNCS_n_p86_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7801LNCS_n_p86_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v7801LNCS_n_p86_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 85257 | ||