Submitted by Aline Batista (alinehb.ufpel@gmail.com) on 2018-04-12T13:54:47Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Marcos_Aurelio_Matos_Lemoes.pdf: 1674974 bytes, checksum: 4f393b06817a591cbb3e8641e9a32578 (MD5) / Made available in DSpace on 2018-04-12T14:56:14Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Marcos_Aurelio_Matos_Lemoes.pdf: 1674974 bytes, checksum: 4f393b06817a591cbb3e8641e9a32578 (MD5) Previous issue date: 2016-12-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / A presente tese foi construída a partir de um recorte da pesquisa realizada na fronteira entre o Brasil e o Uruguai intitulada “Identificação de Indicadores para o monitoramento e avaliação dos impactos da nova política uruguaia de regulação do mercado de Cannabis sobre a saúde pública e o consumo de drogas na zona de fronteira entre Brasil e Uruguai” financiada pela Secretaria Nacional de Drogas do Ministério da Justiça SENAD/MJ. Utilizou-se o banco de dados qualitativo de municípios pesquisados sobre o eixo saúde pública. O estudo buscou reconhecer como se produz no cotidiano da gestão, regiões de saúde em municípios considerados cidades gêmeas entre o Brasil e o Uruguai. Na pesquisa foram entrevistados gestores municipais e gestores de saúde do Brasil e do Uruguai totalizando 14 municípios. A coleta de dados deu-se por entrevista semiestruturada com perguntas abertas sobre gestão em saúde e questões fechadas para realizar a caracterização do município e perfil dos participantes. Para este estudo optou-se por realizar a análise de conteúdo proposta por Bardin, (2011). Neste método foram designados três polos cronológicos a pré analise, a exploração do material e o tratamento dos resultados a inferência e a interpretação. No estudo optou-se como referencial teórico o Postulado de coerência de Carlos Matus e Mário Testa e a proposta teórica de Rogério Haesbaert para a multiterritorialidade. A coleta de dados deu-se após aprovação do Comitê de ética e Pesquisa parecer número1.757.934 no mês de outubro de 2016. Verificou-se que os gestores destes municípios enfrentam diariamente a fluidez do espaço utilizado por usuários nacionais e estrangeiros que utilizam os serviços de saúde para sanar os problemas de saúde. Por ser considerada uma fronteira aberta, é difícil ordenar e quantificar os atendimentos a estrangeiros, fato este que incide nos registros e sistemas de informações do Ministério da Saúde por indisponibilidade de alimentação de dados sobre estrangeiros. Os atendimentos na maioria nos municípios ainda ocorrem em situações de urgência e emergência, com vínculos precários e baixa cooperação entre os países. Os gestores anunciam que se utilizam do poder político para definir a contratação de médicos uruguaios e aderir ao Programa Mais Médicos, acarretando disputas judiciais com o Sindicato Medico do Rio Grande do Sul. A definição estratégica e forma de implementação de políticas, são definidas por uma visão intrínseca e fortemente vinculada ao sub financiamento da saúde. / This thesis was built from part of a research carried out along the border between Brazil and Uruguay titled “identifying indicators for monitoring and evaluating the new Uruguayan political impacts on public health and drug consumption caused by the cannabis market regulation along the border area between Brazil and Uruguay" funded by the National Secretariat of Drugs of the Ministry of Justice SENAD / MJ. The aim of the study was to understand the formation of health regions from the Situational strategic planning in twin cities between Brazil and Uruguay. It was used a qualitative database of the cities searched on the axis public health. In the survey, the respondents were municipal managers and health managers in Brazil and Uruguay totaling 14 municipalities. Data collection occurred by semistructured interview with open questions on health management and closed questions designed to perform the characterization of the city and profile of participants. For this study it was decided to carry out the content analysis proposed by Bardin (2011). It was chosen also as a theoretical basis, the Postulate of Coherence of Carlos Matus and Mario Testa, and, the theoretical proposal of Rogério Haesbaert for multiterritoriality. Data collection occurred after approval by the Ethics and Research Committee Opinion number 1,757,934 in October 2016. It was found that the managers of those cities daily face the fluidity of space used by domestic and foreign users who use health services to address the health problems. Because it is considered an open border, it is difficult to sort and quantify the calls to foreigners, a fact that focuses on the records and information systems of the Ministry of Health, due to the unavailability of data on foreign supply. The health calls in most cities still occur in urgent and emergency situations, with poor bonds and low cooperation between the countries. Managers claim about the use of political power to set the hiring of Uruguayan doctors and to join the More Doctors – a Brazilian Program - causing disputes with the Medical Union of Rio Grande do Sul state. The strategic definition and form of policy implementation are defined by an intrinsic vision and are strongly linked to the health underfunding.

Movimentos mundiais vêm, através do tempo ampliando os conceitos do processo saúde/doença acrescentando o contexto biopsicosocial e econômico, aumentando as exigências de atuação no setor de saúde. As novas exigências, legalmente compostas, levam à necessidade de novos contornos na administração, no planejamento e na política municipal. Sob a justificativa de avançar no cumprimento das diretrizes constitucionais, na consolidação do processo de descentralização exigido pelo Sistema Único de Saúde, e de direcionar esforços intersetoriais que possam garantir a integralidade das ações em saúde, está pesquisa objetiva, num primeiro momento, analisar a percepção relativa ao conceito de saúde/doença nos vários níveis do governo municipal e o relacionamento do setor de trabalho na gestão pública, com a área de saúde, verificando a viabilidade do trabalho intersetorial no contexto político-organizacional, e num segundo momento, esclarecidos sobre as conclusões e objetivos da pesquisa 1, analisar a percepção sobre a importância do trabalho intersetorial como estratégia para a promoção da integralidade das ações em saúde; após o esclarecimento sobre as conclusões e objetivos da pesquisa 1. O método qualitativo de análise utilizou, nas duas etapas, entrevista individual e aplicação de questionário com questões abertas para a pesquisa 1 e para a pesquisa 2, gravadas no local de trabalho, utilizando a técnica do Discurso do Sujeito Coletivo, para construção da caracterização e análise dos depoimentos verbais, pelas idéias centrais e suas correspondentes expressões chaves. Os sujeitos da pesquisa foram 100 por cento dos elementos envolvidos na gestão municipal, mais dois assessores diretos, localizados em um município da 13ª Região Sanitária do Rio Grande do Sul. Observou-se no grupo pesquisado a cencepção do conceito de saúde ampliado e positivo; o reconhecimento da responsabilidade dos vários setores sobre o processo saúde/doença da população e a afirmação da possibilidade de trabalho intersetorial; e conclui-se que com mudanças político-organizacionais, capacitação de recursos humanos, e planejamento, pode-se alcançar melhoria na ações de promoção da integralidade das ações em saúde / World movements have been, through time, widening the concept of the health-disease process, adding to it the idea of the biopsychosocial and economic context, and increasing the demands for action in the health area. To answer these new demands which have legal support, there is also the need for new trends in administration, planning and local politics. Implementation of the principles of the Constitution, consolidation of the process of descentralization in the Brazilian Health System (SUS) and development of joint action by different sectors are the fundamentals of the present research, whose objective is, first, to study the perception relative to the health-disease process in the different levels of the local government and also the relationship of the labour sector with the health sector, in order to disclose the possibility of political and organizational cooperation between these two sectors; and second, to analyze the perception of the relevance of cooperation among sectors as a strategy for promoting integrality of health actions. The Qualitative Method of Analysis consisted, in these two phases, of individual interviews and applcation of a survey for research 1 and research 2 with open questions, recorded at the work place. A transcription was then made, utilizing the Collective Subject Discourse tehnique, which allows characterization and analysis of oral testimonies, based on central ideas and key-expression. 100 per cent of the members of the health administrative staff in a county of the 13rd Health Region of Rio Grande do Sul, plus two direct consultants, were interviwed. We noticed that they have a non-limited and positive concept of health; that they recognize the responsibility of several sectors in the health-disease process in the population and that they also recognize the possibility of joint cooperation among sectors. Based on these fidings we can assure that, with political and administrative changes, capacitation of human resources and planning it is possible to promote and to improve actions to increase integrality in health care.

Esta dissertação se propõe a produzir uma reflexão sobre as implicações da macropolítica nacional e da micropolítica local na organização de processos regulatórios no âmbito municipal. Para análise dos aspectos da macropolítica que interferem nos processos regulatórios municipais foi realizada uma revisão da literatura sobre o tema. Para compreender os processos da micropolítica que envolvem a regulação foi utilizada a metodologia de casos traçadores, na qual foram selecionados dois casos envolvendo serviços de saúde do município e a intermediação do Complexo Regulador. Foram realizadas entrevistas com profissionais e os usuários envolvidos explorando as situações vividas e analisando os seus percursos pelo sistema. A partir desse material foi realizada uma análise da construção e implantação dos processos regulatórios em saúde no município de Guarulhos e suas implicações na organização da rede de serviços, no acesso da população aos serviços e na gestão do cuidado. Observou-se a necessidade de ampliar o diálogo entre a regulação, outros serviços e profissionais da rede no campo da micropolítica das organizações e da produção do cuidado. Reconhecer que a organização da assistência é produto da interação entre os atores sociais e políticos envolvidos no ato do cuidado é um importante passo na busca da integralidade. Para ampliar a possibilidade de resposta às necessidades do usuário é necessário buscar dispositivos de cogestão que propiciem espaços permanentes de diálogo e identifiquem potencialidades para novos arranjos / This dissertation aims to produce a reflection on the implications of the national macropolitics and local micropolitics on the organization of regulatory processes at municipal level. For analysis of the macropolitics aspects that interfere in municipal regulatory processes, a literature review of the topic was conducted. To understand the processes that involve micropolitics and regulatory processes the methodology of adjustment was used in selected cases, which were selected in two cases involving the municipal health services and intermediation of the Complexo Regulador. Interviews were conducted with professionals and users involved exploring the lived situations and analyzing their paths through the health system. From this material, an analysis of the construction and implementation of the regulatory processes in health was performed in the city of Guarulhos and its implications for the organization of the network services, the population\'s access to healthcare services and care management. There is a need to expand the dialogue between the regulation, other healthcare services and network professionals, organizations and care production in the field of micropolitics. Recognize that the organization of care is the product of the interaction between social and political actors involved in the act of care is an important step towards integrality. To enlarge the ability to meet the needs of the user is necessary to seek co-management devices that provide permanent spaces for dialogue and identify potential new arrangements

Um dos focos da saúde pública na atualidade são as doenças crônicas não transmissíveis, como a hipertensão arterial sistêmica e o diabetes mellitus. Estas são frequentes na atenção básica e, principal público das equipes de saúde da família. O acompanhamento inadequado destas acarreta em prejuízos à saúde da pessoa e altos custos ao sistema de saúde. Diante da dificuldade das equipes da estratégia saúde da família ofertarem atenção integral a hipertensos e diabéticos, buscou-se compreender o fenômeno. Dentre os princípios do SUS, a integralidade norteou as discussões desta pesquisa, baseando-se nos sentidos propostos por Mattos (boa medicina, forma de organizar o sistema de saúde e políticas especiais). Este estudo objetivou identificar e analisar as ações realizadas pelas equipes de saúde da família para o acompanhamento e cuidado integral dos indivíduos com hipertensão arterial sistêmica e diabetes melittus tipo 2 em um município do interior do Estado de São Paulo. Bem como identificar os instrumentos utilizados, e as dificuldades enfrentadas pelas mesmas neste processo. Utilizou-se abordagem qualitativa, e a técnica grupo focal para coleta de dados, além de instrumento para caracterização dos sujeitos. Foram selecionadas três equipes, por meio da nota atribuída pelas mesmas na autoavaliação do PMAQ, com intuito de apreender dificuldades distintas. O material transcrito foi submetido à análise de conteúdo temática, da qual emergiram três grandes temas: concepções dos profissionais sobre o trabalho em saúde, ações e dificuldades para o acompanhamento e cuidado integral de hipertensos e diabéticos. As ações identificadas foram orientações, visitas domiciliares, consultas, considerar a família para propor o cuidado, intersetorialidade e construção de vínculo. A comparação entre estas e aquelas preconizadas pela Secretaria do Estado de São Paulo evidenciou lacunas na assistência prestada a esta população, sendo estas justificadas por dificuldades relativas à falta de recursos, processo de trabalho e resistências dos usuários. A equipe com a maior nota no AMAQ, embora esteja inserida na mesma realidade municipal, parece encarar as dificuldades com mais naturalidade, enquanto as outras evidenciam o problema e se paralisam. Esta, no entanto, possui três pontos importantes a seu favor, estrutura física adequada, ausência de interferência do modelo assistencial proposto pela UBS tradicional, maior escolaridade e formação mais adequada à estratégia saúde da família. A sistematização dos problemas obtida neste estudo beneficia o município, pois embasa plano de intervenções, com vistas a uma assistência à saúde integral e de qualidade a esta população. Para isso, propõe oficinas que visam ampliar a compreensão dos trabalhadores sobre o modelo assistencial proposto pela Saúde da Família, sensibilizando-os para as práticas integrais a hipertensos e diabéticos, consolidando assim a atenção básica como coordenadora do cuidado no SUS / One of the focuses of public health today are the chronic diseases such as hypertension and diabetes mellitus. These are common in primary care and primary audience of family health teams. Inadequate monitoring of these causes in damage to the person\'s health and high costs to the health system. Given the difficulty of the teams of the family health strategy an offer comprehensive care for hypertension and diabetes, we tried to understand the phenomenon. Among the principles of SUS, completeness guided the discussions of this research, based on the senses proposed by Mattos (good medicine, how to organize the health system and special policies). This study aimed to identify and analyze the actions taken by family health teams for monitoring and comprehensive care of people with hypertension and diabetes mellitus type 2 in a municipality in the state of São Paulo. And to identify the instruments used, and the difficulties faced by them in this process. We used a qualitative approach, and the focus group technique for data collection, as well as instrument to characterize the subjects. Three teams were selected by the score given by them for self- assessment of PMAQ, aiming to apprehend distinct difficulties. The transcribed material was submitted to thematic content analysis, which emerged three major themes: views of professionals on the health work, actions and difficulties in monitoring and comprehensive care of hypertension and diabetes. The actions were identified guidelines, home visits, consultations, consider the family to propose care, intersectoral and construction bond. The comparison between these and those recommended by the Secretary of State of São Paulo showed gaps in assistance to this population, which are justified by difficulties regarding the lack of resources, work process and resistance from users. The team with the highest score in AMAQ, although it is inserted in the same municipal reality seems to face difficulties more naturally, while others highlight the problem and paralyze. This, however, has three important points in its favor, adequate physical structure, the absence of interference of the care model proposed by traditional UBS, higher education and training best suited to the family health strategy. The systematization of the problems found in this study benefits the municipality because underlies intervention plan with a view to a support comprehensive health and quality to this population. It is proposed to workshops aimed at raising understanding of the workers on the care model proposed by Family Health, making them aware of the comprehensive practices to hypertension and diabetes, thereby enhancing primary care as coordinator of care in the SUS

Um dos focos da saúde pública na atualidade são as doenças crônicas não transmissíveis, como a hipertensão arterial sistêmica e o diabetes mellitus. Estas são frequentes na atenção básica e, principal público das equipes de saúde da família. O acompanhamento inadequado destas acarreta em prejuízos à saúde da pessoa e altos custos ao sistema de saúde. Diante da dificuldade das equipes da estratégia saúde da família ofertarem atenção integral a hipertensos e diabéticos, buscou-se compreender o fenômeno. Dentre os princípios do SUS, a integralidade norteou as discussões desta pesquisa, baseando-se nos sentidos propostos por Mattos (boa medicina, forma de organizar o sistema de saúde e políticas especiais). Este estudo objetivou identificar e analisar as ações realizadas pelas equipes de saúde da família para o acompanhamento e cuidado integral dos indivíduos com hipertensão arterial sistêmica e diabetes melittus tipo 2 em um município do interior do Estado de São Paulo. Bem como identificar os instrumentos utilizados, e as dificuldades enfrentadas pelas mesmas neste processo. Utilizou-se abordagem qualitativa, e a técnica grupo focal para coleta de dados, além de instrumento para caracterização dos sujeitos. Foram selecionadas três equipes, por meio da nota atribuída pelas mesmas na autoavaliação do PMAQ, com intuito de apreender dificuldades distintas. O material transcrito foi submetido à análise de conteúdo temática, da qual emergiram três grandes temas: concepções dos profissionais sobre o trabalho em saúde, ações e dificuldades para o acompanhamento e cuidado integral de hipertensos e diabéticos. As ações identificadas foram orientações, visitas domiciliares, consultas, considerar a família para propor o cuidado, intersetorialidade e construção de vínculo. A comparação entre estas e aquelas preconizadas pela Secretaria do Estado de São Paulo evidenciou lacunas na assistência prestada a esta população, sendo estas justificadas por dificuldades relativas à falta de recursos, processo de trabalho e resistências dos usuários. A equipe com a maior nota no AMAQ, embora esteja inserida na mesma realidade municipal, parece encarar as dificuldades com mais naturalidade, enquanto as outras evidenciam o problema e se paralisam. Esta, no entanto, possui três pontos importantes a seu favor, estrutura física adequada, ausência de interferência do modelo assistencial proposto pela UBS tradicional, maior escolaridade e formação mais adequada à estratégia saúde da família. A sistematização dos problemas obtida neste estudo beneficia o município, pois embasa plano de intervenções, com vistas a uma assistência à saúde integral e de qualidade a esta população. Para isso, propõe oficinas que visam ampliar a compreensão dos trabalhadores sobre o modelo assistencial proposto pela Saúde da Família, sensibilizando-os para as práticas integrais a hipertensos e diabéticos, consolidando assim a atenção básica como coordenadora do cuidado no SUS / One of the focuses of public health today are the chronic diseases such as hypertension and diabetes mellitus. These are common in primary care and primary audience of family health teams. Inadequate monitoring of these causes in damage to the person\'s health and high costs to the health system. Given the difficulty of the teams of the family health strategy an offer comprehensive care for hypertension and diabetes, we tried to understand the phenomenon. Among the principles of SUS, completeness guided the discussions of this research, based on the senses proposed by Mattos (good medicine, how to organize the health system and special policies). This study aimed to identify and analyze the actions taken by family health teams for monitoring and comprehensive care of people with hypertension and diabetes mellitus type 2 in a municipality in the state of São Paulo. And to identify the instruments used, and the difficulties faced by them in this process. We used a qualitative approach, and the focus group technique for data collection, as well as instrument to characterize the subjects. Three teams were selected by the score given by them for self- assessment of PMAQ, aiming to apprehend distinct difficulties. The transcribed material was submitted to thematic content analysis, which emerged three major themes: views of professionals on the health work, actions and difficulties in monitoring and comprehensive care of hypertension and diabetes. The actions were identified guidelines, home visits, consultations, consider the family to propose care, intersectoral and construction bond. The comparison between these and those recommended by the Secretary of State of São Paulo showed gaps in assistance to this population, which are justified by difficulties regarding the lack of resources, work process and resistance from users. The team with the highest score in AMAQ, although it is inserted in the same municipal reality seems to face difficulties more naturally, while others highlight the problem and paralyze. This, however, has three important points in its favor, adequate physical structure, the absence of interference of the care model proposed by traditional UBS, higher education and training best suited to the family health strategy. The systematization of the problems found in this study benefits the municipality because underlies intervention plan with a view to a support comprehensive health and quality to this population. It is proposed to workshops aimed at raising understanding of the workers on the care model proposed by Family Health, making them aware of the comprehensive practices to hypertension and diabetes, thereby enhancing primary care as coordinator of care in the SUS

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

This thesis has two parts. In the first part, we study some graph covering problems with a non-local covering rule that allows a "remote" node to be covered by repeatedly applying the covering rule. In the second part, we provide some results on the packing of Steiner trees. In the Propagation problem we are given a graph $G$ and the goal is to find a minimum-sized set of nodes $S$ that covers all of the nodes, where a node $v$ is covered if (1) $v$ is in $S$, or (2) $v$ has a neighbor $u$ such that $u$ and all of its neighbors except $v$ are covered. Rule (2) is called the propagation rule, and it is applied iteratively. Throughout, we use $n$ to denote the number of nodes in the input graph. We prove that the path-width parameter is a lower bound for the optimal value. We show that the Propagation problem is NP-hard in planar weighted graphs. We prove that it is NP-hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in weighted (general) graphs. The second problem that we study is the Power Dominating Set problem. This problem has two covering rules. The first rule is the same as the domination rule as in the Dominating Set problem, and the second rule is the same propagation rule as in the Propagation problem. We show that it is hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in general graphs. We design and analyze an approximation algorithm with a performance guarantee of $O(\sqrt{n})$ on planar graphs. We formulate a common generalization of the above two problems called the General Propagation problem. We reformulate this general problem as an orientation problem, and based on this reformulation we design a dynamic programming algorithm. The algorithm runs in linear time when the graph has tree-width $O(1)$. Motivated by applications, we introduce a restricted version of the problem that we call the $\ell$-round General Propagation problem. We give a PTAS for the $\ell$-round General Propagation problem on planar graphs, for small values of $\ell$. Our dynamic programming algorithms and the PTAS can be extended to other problems in networks with similar propagation rules. As an example we discuss the extension of our results to the Target Set Selection problem in the threshold model of the diffusion processes. In the second part of the thesis, we focus on the Steiner Tree Packing problem. In this problem, we are given a graph $G$ and a subset of terminal nodes $R\subseteq V(G)$. The goal in this problem is to find a maximum cardinality set of disjoint trees that each spans $R$, that is, each of the trees should contain all terminal nodes. In the edge-disjoint version of this problem, the trees have to be edge disjoint. In the element-disjoint version, the trees have to be node disjoint on non-terminal nodes and edge-disjoint on edges adjacent to terminals. We show that both problems are NP-hard when there are only $3$ terminals. Our main focus is on planar instances of these problems. We show that the edge-disjoint version of the problem is NP-hard even in planar graphs with $3$ terminals on the same face of the embedding. Next, we design an algorithm that achieves an approximation guarantee of $\frac{1}{2}-\frac{1}{k}$, given a planar graph that is $k$ element-connected on the terminals; in fact, given such a graph the algorithm returns $k/2-1$ element-disjoint Steiner trees. Using this algorithm we get an approximation algorithm with guarantee of (almost) $4$ for the edge-disjoint version of the problem in planar graphs. We also show that the natural LP relaxation of the edge-disjoint Steiner Tree Packing problem has an integrality ratio of $2-\epsilon$ in planar graphs.

This thesis has two parts. In the first part, we study some graph covering problems with a non-local covering rule that allows a "remote" node to be covered by repeatedly applying the covering rule. In the second part, we provide some results on the packing of Steiner trees. In the Propagation problem we are given a graph $G$ and the goal is to find a minimum-sized set of nodes $S$ that covers all of the nodes, where a node $v$ is covered if (1) $v$ is in $S$, or (2) $v$ has a neighbor $u$ such that $u$ and all of its neighbors except $v$ are covered. Rule (2) is called the propagation rule, and it is applied iteratively. Throughout, we use $n$ to denote the number of nodes in the input graph. We prove that the path-width parameter is a lower bound for the optimal value. We show that the Propagation problem is NP-hard in planar weighted graphs. We prove that it is NP-hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in weighted (general) graphs. The second problem that we study is the Power Dominating Set problem. This problem has two covering rules. The first rule is the same as the domination rule as in the Dominating Set problem, and the second rule is the same propagation rule as in the Propagation problem. We show that it is hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in general graphs. We design and analyze an approximation algorithm with a performance guarantee of $O(\sqrt{n})$ on planar graphs. We formulate a common generalization of the above two problems called the General Propagation problem. We reformulate this general problem as an orientation problem, and based on this reformulation we design a dynamic programming algorithm. The algorithm runs in linear time when the graph has tree-width $O(1)$. Motivated by applications, we introduce a restricted version of the problem that we call the $\ell$-round General Propagation problem. We give a PTAS for the $\ell$-round General Propagation problem on planar graphs, for small values of $\ell$. Our dynamic programming algorithms and the PTAS can be extended to other problems in networks with similar propagation rules. As an example we discuss the extension of our results to the Target Set Selection problem in the threshold model of the diffusion processes. In the second part of the thesis, we focus on the Steiner Tree Packing problem. In this problem, we are given a graph $G$ and a subset of terminal nodes $R\subseteq V(G)$. The goal in this problem is to find a maximum cardinality set of disjoint trees that each spans $R$, that is, each of the trees should contain all terminal nodes. In the edge-disjoint version of this problem, the trees have to be edge disjoint. In the element-disjoint version, the trees have to be node disjoint on non-terminal nodes and edge-disjoint on edges adjacent to terminals. We show that both problems are NP-hard when there are only $3$ terminals. Our main focus is on planar instances of these problems. We show that the edge-disjoint version of the problem is NP-hard even in planar graphs with $3$ terminals on the same face of the embedding. Next, we design an algorithm that achieves an approximation guarantee of $\frac{1}{2}-\frac{1}{k}$, given a planar graph that is $k$ element-connected on the terminals; in fact, given such a graph the algorithm returns $k/2-1$ element-disjoint Steiner trees. Using this algorithm we get an approximation algorithm with guarantee of (almost) $4$ for the edge-disjoint version of the problem in planar graphs. We also show that the natural LP relaxation of the edge-disjoint Steiner Tree Packing problem has an integrality ratio of $2-\epsilon$ in planar graphs.

A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.