Registro completo de metadatos
| Campo DC | Valor | Lengua/Idioma |
|---|---|---|
| dc.creator | Lin, Min Chih | - |
| dc.creator | Mizrahi, Michel Jonathan | - |
| dc.creator | Szwarcfiter, Jayme L. | - |
| dc.date | 2018-01-11T21:14:56Z | - |
| dc.date | 2018-01-11T21:14:56Z | - |
| dc.date | 2014-05 | - |
| dc.date | 2018-01-11T19:35:54Z | - |
| dc.date.accessioned | 2019-04-29T15:26:44Z | - |
| dc.date.available | 2019-04-29T15:26:44Z | - |
| dc.date.issued | 2014-05 | - |
| dc.identifier | Mizrahi, Michel Jonathan; Szwarcfiter, Jayme L.; Lin, Min Chih; Fast algorithms for some dominating induced matching problems; Elsevier Science; Information Processing Letters; 114; 10; 5-2014; 524-528 | - |
| dc.identifier | 0020-0190 | - |
| dc.identifier | http://hdl.handle.net/11336/33031 | - |
| dc.identifier | CONICET Digital | - |
| dc.identifier | CONICET | - |
| dc.identifier.uri | http://rodna.bn.gov.ar:8080/jspui/handle/bnmm/294287 | - |
| dc.description | We describe O(n) time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n) bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n + m) time algorithms we show that they can be reduced to O(n) time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n2) to O(n), while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM’s of the given graph. | - |
| dc.description | Fil: Lin, Min Chih. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | - |
| dc.description | Fil: Mizrahi, Michel Jonathan. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | - |
| dc.description | Fil: Szwarcfiter, Jayme L.. Instituto Nacional de Metrologia, Qualidade e Tecnologia; Brasil | - |
| dc.format | application/pdf | - |
| dc.format | application/pdf | - |
| dc.language | eng | - |
| dc.publisher | Elsevier Science | - |
| dc.relation | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2014.04.012 | - |
| dc.relation | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S002001901400091X | - |
| dc.rights | info:eu-repo/semantics/restrictedAccess | - |
| dc.rights | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | - |
| dc.source | reponame:CONICET Digital (CONICET) | - |
| dc.source | instname:Consejo Nacional de Investigaciones Científicas y Técnicas | - |
| dc.source | instacron:CONICET | - |
| dc.subject | Algorithms | - |
| dc.subject | Dominating induced matchings | - |
| dc.subject | Graph theory | - |
| dc.subject | Matemática Pura | - |
| dc.subject | Matemáticas | - |
| dc.subject | CIENCIAS NATURALES Y EXACTAS | - |
| dc.subject | Ciencias de la Computación | - |
| dc.subject | Ciencias de la Computación e Información | - |
| dc.subject | CIENCIAS NATURALES Y EXACTAS | - |
| dc.title | Fast algorithms for some dominating induced matching problems | - |
| dc.type | info:eu-repo/semantics/article | - |
| dc.type | info:eu-repo/semantics/publishedVersion | - |
| dc.type | info:ar-repo/semantics/articulo | - |
| Aparece en las colecciones: | CONICET | |
Ficheros en este ítem:
No hay ficheros asociados a este ítem.