| Texto completo | |
| Autor(es): |
Ravelo, Santiago Valdes
;
Miyazawa, Flavio K.
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2025; v. 15536, p. 11-pg., 2025-01-01. |
| Resumo | |
The Maximum Weighted Graph Set Packing (MaxGP) problem is defined as follows: given a graph. G, a set G of subgraphs of G, and a weight function omega : G -> Q(+), the objective is to find a subset S subset of G that maximizes Sigma(H is an element of S)omega(H) and ensures that each pair of elements in S are edge-disjoint. This work introduces MaxGP and three specific cases of the problem, where G contains only subgraphs from a particular class: stars (MaxSP), paths (MaxPP), or triangles (MaxTP). For the unweighted versions of these problems (where (H) = 1 for all H is an element of G), we derived several intractability and inapproximability results. We proved that both unweighted MaxSP and unweighted MaxPP are W[1]-hard and APX-hard, even when the maximum degree of.G is restricted to 3. Additionally, we demonstrated that these two problems are not fixed-parameter tractable (FPT) when parameterized by the treewidth or the maximum degree of G, but they do admit fixedparameter algorithms when parameterized by both treewidth and maximum degree. For MaxTP, we showed the existence of a fixed-parameter algorithm when parameterized solely by the treewidth of G. Moreover, we proved that the unweighted versions of MaxSP, MaxPP, and MaxTP are NP-hard on planar graphs. Using our FPT results, we proposed polynomial-time approximation schemes (PTASs) for these versions on planar graphs. (AU) | |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 22/06728-5 - Algoritmos para Problemas de Empacotamento |
| Beneficiário: | Santiago Valdés Ravelo |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Processo FAPESP: | 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos |
| Beneficiário: | Reinaldo Morabito Neto |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |