http://sedici.unlp.edu.ar:80/handle/10915/94283 2026-10-14T11:32:14Z 2026-10-14T11:32:14Z Tapasco, Omar Giraldo, Jaime Toro N., Carlos http://sedici.unlp.edu.ar:80/handle/10915/94595 2020-04-30T04:03:09Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) El presente trabajo hace relación a resultados parciales de investigación, conducentes a la obtención de indicadores de desempeño en sistemas de transporte público, desde los enfoques analítico y de simulación. Para ello se toma como caso de estudio el análisis de desempeño del sistema de transporte del Cable Aéreo de Manizales, Colombia, con la aplicación del modelo teórico de redes abiertas de Jackson, y haciendo uso del programa Promodel desde la perspectiva de la simulación discreta. Los resultados arrojan que desde ambas perspectivas de estudio, se obtiene una baja tasa de uso del sistema de transporte.

2013-01-01T00:00:00Z El presente trabajo hace relación a resultados parciales de investigación, conducentes a la obtención de indicadores de desempeño en sistemas de transporte público, desde los enfoques analítico y de simulación. Para ello se toma como caso de estudio el análisis de desempeño del sistema de transporte del Cable Aéreo de Manizales, Colombia, con la aplicación del modelo teórico de redes abiertas de Jackson, y haciendo uso del programa Promodel desde la perspectiva de la simulación discreta. Los resultados arrojan que desde ambas perspectivas de estudio, se obtiene una baja tasa de uso del sistema de transporte. Sagula, Jorge E. Teseyra, René J. http://sedici.unlp.edu.ar:80/handle/10915/94593 2020-04-30T04:03:09Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) En este artículo se introduce un algoritmo de búsqueda que combina características de Métodos de Búsqueda en Haz y Búsqueda Voraz, juntamente con métodos de Decisión Multicriterio con el propósito de resolver problemas de búsqueda de rutas con restricciones de preferencias, donde los puntos se organizan en un multigrafo masivamente conectado, tal que esta representación resulta adecuada para modelar situaciones reales (o en su defecto, aproximaciones a la realidad). Además, en el enfoque propuesto se intenta dar una respuesta a situaciones en las cuales no es posible hallar una forma de conexión entre el nodo origen y el nodo destino respetando las preferencias introducidas por un usuario; al efecto, se emplean técnicas de determinación de proximidad denominadas K-ésimo Vecino Más Cercano para hallar una locación lo más cercana posible que satisfaga los requerimientos impuestos por las preferencias de usuario.; This article introduces a search algorithm that combines characteristics of Beam-Search and Voraqcious-Search methods, together with Multicriteria Decision methods with the purpose of solving search problems constrained routing preferences, where the points are arranged in a massively connected multigraph, such that this representation is suitable for modeling real situations (or failing that, approximations of reality). Furthermore, the proposed approach tries to respond to situations in which it is possible to find a form of connection between the source node and the destination node respecting the preferences introduced by a user, the purpose, techniques used for determining proximity called K-th nearest Neighbor to find a location as close as possible to meet the requirements imposed by the user preferences.

2013-01-01T00:00:00Z En este artículo se introduce un algoritmo de búsqueda que combina características de Métodos de Búsqueda en Haz y Búsqueda Voraz, juntamente con métodos de Decisión Multicriterio con el propósito de resolver problemas de búsqueda de rutas con restricciones de preferencias, donde los puntos se organizan en un multigrafo masivamente conectado, tal que esta representación resulta adecuada para modelar situaciones reales (o en su defecto, aproximaciones a la realidad). Además, en el enfoque propuesto se intenta dar una respuesta a situaciones en las cuales no es posible hallar una forma de conexión entre el nodo origen y el nodo destino respetando las preferencias introducidas por un usuario; al efecto, se emplean técnicas de determinación de proximidad denominadas K-ésimo Vecino Más Cercano para hallar una locación lo más cercana posible que satisfaga los requerimientos impuestos por las preferencias de usuario. This article introduces a search algorithm that combines characteristics of Beam-Search and Voraqcious-Search methods, together with Multicriteria Decision methods with the purpose of solving search problems constrained routing preferences, where the points are arranged in a massively connected multigraph, such that this representation is suitable for modeling real situations (or failing that, approximations of reality). Furthermore, the proposed approach tries to respond to situations in which it is possible to find a form of connection between the source node and the destination node respecting the preferences introduced by a user, the purpose, techniques used for determining proximity called K-th nearest Neighbor to find a location as close as possible to meet the requirements imposed by the user preferences. Rojo, Horacio Ramos, Silvia Adriana González, Xavier Raspa, Leandro Wainstock, Alejandro Kalmus, Darío http://sedici.unlp.edu.ar:80/handle/10915/94590 2020-04-30T04:03:11Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) El objetivo principal del artículo es realizar un análisis de las vulnerabilidades sobre el conjunto inicial de estrategias dentro de una metodología de Decisiones Robustas aplicada en un sistema de producción agrícola. El presente trabajo detalla este aspecto dentro del marco de un proyecto de investigación en el cual se desarrolla en profundidad la temática de las Decisiones Robustas aplicadas a la toma de decisiones de los productores agrícola. Un objetivo secundario es presentar la Metodología de las Decisiones Robustas en un ámbito educativo para que sus resultados puedan ser reproducidos en otros campos de aplicación.; The main objective of the paper is to analyze the vulnerabilities of the initial set of strategies within a Robust Decisions methodology applicable in an agricultural production system. This study details the step of deeply analyzing vulnerabilities within a wider research project in which the Robust Decision Making methodology is analyzed for decision making in agriculture field. A secondary objective is to present the Robust Decision Making methodology from an educational point of view so that anyone will be able to reproduce the results in other field.

2013-01-01T00:00:00Z El objetivo principal del artículo es realizar un análisis de las vulnerabilidades sobre el conjunto inicial de estrategias dentro de una metodología de Decisiones Robustas aplicada en un sistema de producción agrícola. El presente trabajo detalla este aspecto dentro del marco de un proyecto de investigación en el cual se desarrolla en profundidad la temática de las Decisiones Robustas aplicadas a la toma de decisiones de los productores agrícola. Un objetivo secundario es presentar la Metodología de las Decisiones Robustas en un ámbito educativo para que sus resultados puedan ser reproducidos en otros campos de aplicación. The main objective of the paper is to analyze the vulnerabilities of the initial set of strategies within a Robust Decisions methodology applicable in an agricultural production system. This study details the step of deeply analyzing vulnerabilities within a wider research project in which the Robust Decision Making methodology is analyzed for decision making in agriculture field. A secondary objective is to present the Robust Decision Making methodology from an educational point of view so that anyone will be able to reproduce the results in other field. Laux, Válber Lyra, Adria http://sedici.unlp.edu.ar:80/handle/10915/94589 2020-04-30T04:03:12Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) O Problema da Sequência mais Próxima (PSMP) é um problema da Biologia Molecular que aparece no contexto da comparação de sequências. O objetivo é encontrar uma sequência que apresente a menor distância entre todas as sequências de um conjunto dado. O problema foi provado ser NP-difícil. Diversos algoritmos aproximativos, exatos e heurísticos tem sido propostos. Neste trabalho é proposto um algoritmo para o PSMP baseado na metaheurística GRASP, que apresentou soluções de boa qualidade em baixo tempo de execução nos testes realizados.

2013-01-01T00:00:00Z O Problema da Sequência mais Próxima (PSMP) é um problema da Biologia Molecular que aparece no contexto da comparação de sequências. O objetivo é encontrar uma sequência que apresente a menor distância entre todas as sequências de um conjunto dado. O problema foi provado ser NP-difícil. Diversos algoritmos aproximativos, exatos e heurísticos tem sido propostos. Neste trabalho é proposto um algoritmo para o PSMP baseado na metaheurística GRASP, que apresentou soluções de boa qualidade em baixo tempo de execução nos testes realizados. Figueiredo, Danielle Durski Rosário, Raimundo Ronilson Leal do Benevides, Paula Francis Souza, Luzia Vidal de http://sedici.unlp.edu.ar:80/handle/10915/94588 2020-04-30T04:03:13Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) A finalidade do planejamento da rede escolar é o de realizar o atendimento em todas as áreas da cidade, que garanta acesso mais seguro, mais fácil e mais econômico aos alunos. Este trabalho oferece uma avaliação da localização das escolas públicas municipais de Prudentópolis no estado do Paraná, Brasil, baseando-se na situação real e atual apresentada. O estudo oferece a indicação de uma unidade escolar a ser fechada ou remanejada para outros setores, pois atualmente a rede municipal de ensino apresenta excesso de vagas, bem como os custos obtidos com a exclusão da unidade escolar da rede. Resultados da pesquisa mostraram que a localização geográfica atual das escolas municipais está adequada, em relação à soma das distâncias percorridas pelos estudantes até as escolas, pois apresenta pequeno desvio em relação á solução obtida através da metodologia proposta.; The purpose of planning the school system is to perform the service in all areas of the city, which guarantees access safer, easier and more economical to students. This paper provides an assessment of the location of public schools in the municipality of Prudentópolis in Paraná state, Brazil, based on the actual situation and the current displayed. The study provides a reference to a school to be closed or relocated to other sectors, as currently the municipal school has excess vacancies, as well as the costs obtained with the exclusion of the school unit's network. Survey results showed that the current geographical location of the municipal schools is adequate in relation to the sum of the distances traveled by students to schools, it presents small deviation to the solution obtained by the proposed methodology.

2013-01-01T00:00:00Z A finalidade do planejamento da rede escolar é o de realizar o atendimento em todas as áreas da cidade, que garanta acesso mais seguro, mais fácil e mais econômico aos alunos. Este trabalho oferece uma avaliação da localização das escolas públicas municipais de Prudentópolis no estado do Paraná, Brasil, baseando-se na situação real e atual apresentada. O estudo oferece a indicação de uma unidade escolar a ser fechada ou remanejada para outros setores, pois atualmente a rede municipal de ensino apresenta excesso de vagas, bem como os custos obtidos com a exclusão da unidade escolar da rede. Resultados da pesquisa mostraram que a localização geográfica atual das escolas municipais está adequada, em relação à soma das distâncias percorridas pelos estudantes até as escolas, pois apresenta pequeno desvio em relação á solução obtida através da metodologia proposta. The purpose of planning the school system is to perform the service in all areas of the city, which guarantees access safer, easier and more economical to students. This paper provides an assessment of the location of public schools in the municipality of Prudentópolis in Paraná state, Brazil, based on the actual situation and the current displayed. The study provides a reference to a school to be closed or relocated to other sectors, as currently the municipal school has excess vacancies, as well as the costs obtained with the exclusion of the school unit's network. Survey results showed that the current geographical location of the municipal schools is adequate in relation to the sum of the distances traveled by students to schools, it presents small deviation to the solution obtained by the proposed methodology. Cámara, Juan Manuel Baroni, Federico Lerman, Ricardo Chezzi, Carlos María Tymoschuk, Ana Rosa http://sedici.unlp.edu.ar:80/handle/10915/94587 2020-04-30T04:03:14Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) El diseño de sistemas informáticos para comercio electrónico implica desembolsos económicos. Por tanto es importante analizar la posibilidad de obtener beneficios antes de su implementación. Para esto es necesario evaluar el desempeño del sistema no sólo desde una perspectiva informática sino además desde la visión de negocios. La simulación es una herramienta que permite experimentar con configuraciones alternativas de negocio previo a la construcción del sistema. Por ello el objetivo del trabajo es presentar un modelo para simulación de procesos de comercio electrónico construido sobre la base de un método de diseño de sistemas de evento discreto y obtener métricas tecnológicas y de negocios. Discrete Event System Especification (DEVS) es un framework de modelado para simulación de evento discreto, basado en la teoría de sistemas, con recursos para modelar problemas complejos y con capacidades para construir modelos con comportamiento estocástico. Sobre la base de una metodología de diseño de procesos de comercio electrónico orientada a servicios se construye un modelo de simulación para transacciones de comercio electrónico. El modelo consta de un marco experimental, una capa transaccional que define las operaciones de negocios y otra tecnológica que configura la plataforma informática. Para la plataforma informática se propone un modelo en tres capas de servidores Web, de Aplicación y de Base de Datos. La implementación del modelo se realiza con la herramienta DEVSJAVA. Es nuestro principal aporte la estrategia de construcción de modelos DEVS de comercio electrónico que parte de la estrategia de negocios y no sólo contempla los recursos informáticos. Se simula para una carga dada de clientes y se obtienen resultados sobre el tiempo de respuesta de las sesiones de clientes, así como un análisis de las posibilidades de retorno de la inversión. De este modo se pueden simular decisiones de negocio previo a su implementación, considerando el desempeño tecnológico y los resulados de negocios.

2013-01-01T00:00:00Z El diseño de sistemas informáticos para comercio electrónico implica desembolsos económicos. Por tanto es importante analizar la posibilidad de obtener beneficios antes de su implementación. Para esto es necesario evaluar el desempeño del sistema no sólo desde una perspectiva informática sino además desde la visión de negocios. La simulación es una herramienta que permite experimentar con configuraciones alternativas de negocio previo a la construcción del sistema. Por ello el objetivo del trabajo es presentar un modelo para simulación de procesos de comercio electrónico construido sobre la base de un método de diseño de sistemas de evento discreto y obtener métricas tecnológicas y de negocios. Discrete Event System Especification (DEVS) es un framework de modelado para simulación de evento discreto, basado en la teoría de sistemas, con recursos para modelar problemas complejos y con capacidades para construir modelos con comportamiento estocástico. Sobre la base de una metodología de diseño de procesos de comercio electrónico orientada a servicios se construye un modelo de simulación para transacciones de comercio electrónico. El modelo consta de un marco experimental, una capa transaccional que define las operaciones de negocios y otra tecnológica que configura la plataforma informática. Para la plataforma informática se propone un modelo en tres capas de servidores Web, de Aplicación y de Base de Datos. La implementación del modelo se realiza con la herramienta DEVSJAVA. Es nuestro principal aporte la estrategia de construcción de modelos DEVS de comercio electrónico que parte de la estrategia de negocios y no sólo contempla los recursos informáticos. Se simula para una carga dada de clientes y se obtienen resultados sobre el tiempo de respuesta de las sesiones de clientes, así como un análisis de las posibilidades de retorno de la inversión. De este modo se pueden simular decisiones de negocio previo a su implementación, considerando el desempeño tecnológico y los resulados de negocios. Argiroffo, Gabriela http://sedici.unlp.edu.ar:80/handle/10915/94585 2020-04-30T04:03:16Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) Given a graph G and a nonnegative integer number k, a k- dominating set in G is a subset of vertices D such that every vertex in the graph is adjacent to at least k elements of D. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G. This is a natural generalization of the well-known dominating set polytope in graphs. In this work we study the 2-dominating set polytope of trees and we will provide new facet de ning inequalities for it.

2013-01-01T00:00:00Z Given a graph G and a nonnegative integer number k, a k- dominating set in G is a subset of vertices D such that every vertex in the graph is adjacent to at least k elements of D. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G. This is a natural generalization of the well-known dominating set polytope in graphs. In this work we study the 2-dominating set polytope of trees and we will provide new facet de ning inequalities for it. Almeida Ribeiro, Érica Tatiane Rider Flores, Marcos Julio http://sedici.unlp.edu.ar:80/handle/10915/94584 2020-04-30T04:03:17Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) This paper shows the development of a mixed integer second-order conic programming model to solve the allocation problem of fixed or switched capacitors banks in radial electrical distribution systems, with the aims to improve the voltage magnitude profile, reduce the active power losses and minimize the energy losses and investment costs. In the proposed model, the steadystate operation point of the radial distribution system is modeled through linear and second-order conic expressions. The use of second-order conic programming model guarantee convergence to optimality using existing optimization software. The test systems of 70, 136 and 202 nodes are used in order to show the accuracy of the mathematical model, as well as the efficiency of the proposed solution technique.

2013-01-01T00:00:00Z This paper shows the development of a mixed integer second-order conic programming model to solve the allocation problem of fixed or switched capacitors banks in radial electrical distribution systems, with the aims to improve the voltage magnitude profile, reduce the active power losses and minimize the energy losses and investment costs. In the proposed model, the steadystate operation point of the radial distribution system is modeled through linear and second-order conic expressions. The use of second-order conic programming model guarantee convergence to optimality using existing optimization software. The test systems of 70, 136 and 202 nodes are used in order to show the accuracy of the mathematical model, as well as the efficiency of the proposed solution technique. Gutierrez, M. Tondato, Silvia Beatriz http://sedici.unlp.edu.ar:80/handle/10915/94552 2020-04-30T04:03:18Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) An asteroidal triple in a graph G is a set of three non- adjacent vertices such that for any two of them there exists a path be- tween them that does not intersect the neighborhood of the third. Special asteroidal triple in a graph G is an asteroidal triple such that each pair is linked by a special connection. A special asteroidal triples play a central role in a characterization of directed path graphs by Cameron, Hoáng and Lévêque. They also introduce a related notion of asteroidal quadru- ple and conjecture a characterization of rooted path graphs. In its original form this conjecture is not complete, still in leafage four, as was showed in. But, as suggested by the conjecture, a characterization by forbidding particular types of asteroidal quadruples may hold. We prove that the conjecture in the original form is true on directed path graphs with leafage four having two minimal separators with multiplicity two. Thus we build the family of forbidden subgraphs in this case.

2013-01-01T00:00:00Z An asteroidal triple in a graph G is a set of three non- adjacent vertices such that for any two of them there exists a path be- tween them that does not intersect the neighborhood of the third. Special asteroidal triple in a graph G is an asteroidal triple such that each pair is linked by a special connection. A special asteroidal triples play a central role in a characterization of directed path graphs by Cameron, Hoáng and Lévêque. They also introduce a related notion of asteroidal quadru- ple and conjecture a characterization of rooted path graphs. In its original form this conjecture is not complete, still in leafage four, as was showed in. But, as suggested by the conjecture, a characterization by forbidding particular types of asteroidal quadruples may hold. We prove that the conjecture in the original form is true on directed path graphs with leafage four having two minimal separators with multiplicity two. Thus we build the family of forbidden subgraphs in this case. Delle Donne, Diego Marenco, Javier http://sedici.unlp.edu.ar:80/handle/10915/94550 2020-04-30T04:03:19Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) Many variants of the vertex coloring problem have been de ned, such as precoloring extension, μ-coloring, (γ ; μ)-coloring, and list coloring. These problems are NP-hard, as they generalize the classical vertex coloring problem. On the other side, there exist several families of graphs for which some of these problems can be solved in polynomial time. The standard integer programming model for coloring problems uses a binary variable xvc for each vertex v and each color c to indicate whether v is assigned c or not. An extension of this model considers binary variables wc for each color c to indicate whether color c is used or not. In this work we study this formulation for the polynomial cases of the coloring problems mentioned above. In particular, we prove that if the classical vertex coloring problem yields an integer polytope for a family of graphs, then the same holds for μ-coloring, ( γ; μ)-coloring, and list coloring over the same family. We prove that the polytope associated to these problems over trees is integer and that adding the clique inequalities, the resulting polytope is integer over block graphs also. Finally, we give a new family of facet-inducing valid inequalities for the standard formulation and we provide empirical evidence suggesting that this family completely describes the polytope associated to these problems over cycles (and probably cactii graphs).

2013-01-01T00:00:00Z Many variants of the vertex coloring problem have been de ned, such as precoloring extension, μ-coloring, (γ ; μ)-coloring, and list coloring. These problems are NP-hard, as they generalize the classical vertex coloring problem. On the other side, there exist several families of graphs for which some of these problems can be solved in polynomial time. The standard integer programming model for coloring problems uses a binary variable xvc for each vertex v and each color c to indicate whether v is assigned c or not. An extension of this model considers binary variables wc for each color c to indicate whether color c is used or not. In this work we study this formulation for the polynomial cases of the coloring problems mentioned above. In particular, we prove that if the classical vertex coloring problem yields an integer polytope for a family of graphs, then the same holds for μ-coloring, ( γ; μ)-coloring, and list coloring over the same family. We prove that the polytope associated to these problems over trees is integer and that adding the clique inequalities, the resulting polytope is integer over block graphs also. Finally, we give a new family of facet-inducing valid inequalities for the standard formulation and we provide empirical evidence suggesting that this family completely describes the polytope associated to these problems over cycles (and probably cactii graphs). Chezzi, Carlos María Tymoschuk, Ana Rosa Lerman, Ricardo http://sedici.unlp.edu.ar:80/handle/10915/94547 2020-04-30T04:03:20Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) The object of this work is to present a discrete event modelization and simulation method for evaluating performance of electronic commerce transactions at business and computational resources levels in order to predict behaviors and changes in system configuration to optimize investment.

2013-01-01T00:00:00Z The object of this work is to present a discrete event modelization and simulation method for evaluating performance of electronic commerce transactions at business and computational resources levels in order to predict behaviors and changes in system configuration to optimize investment. Argiroffo, G. Leoni, V. Torres, P. http://sedici.unlp.edu.ar:80/handle/10915/94545 2020-04-30T04:03:22Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) In this work we obtain a new graph class where {k}-DOM is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. By relating this problem with k-DOM, we prove that {k}-DOM is polynomial time solvable for strongly chordal graphs. Besides, by expressing the property involved in k-DOM in Counting Monadic Second- order Logic, we obtain that both problems are linear time solvable for bounded tree-width graphs. In this way we enlarge the family of graphs for which k-DOM is polynomial time solvable.

2013-01-01T00:00:00Z In this work we obtain a new graph class where {k}-DOM is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. By relating this problem with k-DOM, we prove that {k}-DOM is polynomial time solvable for strongly chordal graphs. Besides, by expressing the property involved in k-DOM in Counting Monadic Second- order Logic, we obtain that both problems are linear time solvable for bounded tree-width graphs. In this way we enlarge the family of graphs for which k-DOM is polynomial time solvable. Argiroffo, G. Escalante, M. Ugarte, M. E. http://sedici.unlp.edu.ar:80/handle/10915/94544 2020-04-30T04:03:23Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) Domination and its variations arise in many applications, in particular in those involving strategic placement of items at vertices of a network. For general graphs these problems are NP-hard, however, domination in graphs has been shown to be polynomially solvable in several graph classes. In this work we consider a generalization of this problem called k-domination in graphs.

2013-01-01T00:00:00Z Domination and its variations arise in many applications, in particular in those involving strategic placement of items at vertices of a network. For general graphs these problems are NP-hard, however, domination in graphs has been shown to be polynomially solvable in several graph classes. In this work we consider a generalization of this problem called k-domination in graphs. Argiroffo, G. Bianchi, S. Wagler, A. http://sedici.unlp.edu.ar:80/handle/10915/94542 2020-04-30T04:03:23Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for special bipartite graphs and cycles, and discuss further lines of research in order to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework.

2013-01-01T00:00:00Z In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for special bipartite graphs and cycles, and discuss further lines of research in order to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework. Alcón, Liliana Graciela Gutiérrez, Marisa Mazzoleni, María Pía http://sedici.unlp.edu.ar:80/handle/10915/94540 2020-05-14T21:34:27Z 2013-01-01T00:00:00Z

Objeto de conferencia XI Simposio Argentino de Investigación Operativa (SIO) - JAIIO 42 (2013) A graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. The class of graphs which admits a VPT representation in a host tree with maximum degree at most h is denoted by [h,2,1]. In [3], it is shown that the problem of recognizing V PT graphs is polynomial time solvable. In [1], it is proved that the problem of deciding whether a given VPT graph belongs to [h; 2; 1] is NP-complete even when restricted to the class V PT∏ Split without dominated stable vertices. The classes [h; 2; 1], h ≥ 2, are closed by taking induced subgraphs, therefore each one can be characterized by a family of minimal forbidden induced subgraphs. Such a family is know only for h = 2 [4] and there are some partial results for h = 3 [2]. In this paper we associate the minimal forbidden induced subgraphs for [h; 2; 1] which are VPT with (color) h-critical graphs. We describe how to obtain minimal forbidden induced subgraphs from critical graphs, even more, we show that the family of graphs obtained using our procedure is exactly the family of minimal forbidden induced subgraphs which are VPT, split and have no dominated stable vertices. We conjecture that there are no other VPT minimal forbidden induced subgraphs. We also prove that the minimal forbidden induced subgraphs for [h; 2; 1] that are VPT graphs belong to the class [h + 1; 2; 1].

2013-01-01T00:00:00Z A graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. The class of graphs which admits a VPT representation in a host tree with maximum degree at most h is denoted by [h,2,1]. In [3], it is shown that the problem of recognizing V PT graphs is polynomial time solvable. In [1], it is proved that the problem of deciding whether a given VPT graph belongs to [h; 2; 1] is NP-complete even when restricted to the class V PT∏ Split without dominated stable vertices. The classes [h; 2; 1], h ≥ 2, are closed by taking induced subgraphs, therefore each one can be characterized by a family of minimal forbidden induced subgraphs. Such a family is know only for h = 2 [4] and there are some partial results for h = 3 [2]. In this paper we associate the minimal forbidden induced subgraphs for [h; 2; 1] which are VPT with (color) h-critical graphs. We describe how to obtain minimal forbidden induced subgraphs from critical graphs, even more, we show that the family of graphs obtained using our procedure is exactly the family of minimal forbidden induced subgraphs which are VPT, split and have no dominated stable vertices. We conjecture that there are no other VPT minimal forbidden induced subgraphs. We also prove that the minimal forbidden induced subgraphs for [h; 2; 1] that are VPT graphs belong to the class [h + 1; 2; 1].