A feature of minimizing images of a class of binary Markov random field energies is introduced and proved. Using this, the collection of minimizing images of levels of higher order, levelable MRF energies is shown to be a monotone collection. This implies that these images can be combined to give minimizing images of the MRF energy itself. Due to the recent developments, second and third order binary MRF energies of the mentioned class are known to be exactly minimized by maximum flow/minimum cut computations on appropriately constructed graphs. With the aid of these developments an exact and efficient algorithm to minimize levelable second and third order MRF energies, which is composed of a series of maximum flow/minimum cut computations, is proposed and applications of the proposed algorithm to image restoration are given.

[pt] Calcular o valor do fluxo máximo entre um nó origem e um nó destino em uma rede é um problema clássico no contexto de Fluxos em Redes. Sua extensão, chamada de problema do fluxo máximo multiterminal, consiste em achar os valores dos fluxos máximos entre todos os pares de nós de uma rede não direcionada. Estes problemas possuem diversas aplicações, especialmente nos campos de transporte, logística, telecomunicações e energia. Neste trabalho, apreciamos a recente teoria da análise de sensibilidade, em que se estuda a influência da variação de capacidade de arestas nos fluxos máximos multiterminais, e estendemos a computação dinâmica dos fluxos multiterminais para o caso de mais de uma aresta com capacidade variável. Através dessa teoria, relacionamos também nós de corte e fluxos multiterminais, o que permitiu desenvolver um método competitivo para solucionar o problema do fluxo máximo multiterminal, quando a rede possui nós de corte. Os resultados dos experimentos computacionais conduzidos com o método proposto são apresentados e comparados com os de um algoritmo clássico, fazendo uso de instâncias geradas e outras conhecidas da literatura. Por último, aplicamos a teoria apresentada em um problema de identificação de complexos de proteínas em redes de interação proteína-proteína. Através da generalização de um algoritmo e de um resultado teórico sobre exclusão de cortes mínimos, foi possível reduzir o número de cálculos de fluxo máximo necessários para identificar tais complexos. / [en] Computing the maximum flow value between a source and a terminal nodes in a given network is a classic problem in the context of network flows. Its extension, namely the multi-terminal maximum flow problem, consists of finding the maximum flow values between the all pairs of nodes in a given undirected network. These problems have several applications, especially in the fields of transports, logistics, telecommunications and energy. In this work, we study the recent theory of sensitivity analysis, which examines the influence of edges capacity variation on the multi-terminals maximum flows, and we extend the dynamic computation of multi-terminals flows to the case of more than one edge with variable capacity. Based on this theory, we also relate cut nodes and multiterminals flows, allowing us to develop a competitive method to solve the multiterminal maximum flow problem, when the network has cut nodes. The results of the computational experiments conducted with the proposed method are presented and compared with the results of a classical algorithm, using generated and wellknown instances of the literature. Finally, we apply the presented theory on a problem of identifying protein complexes in protein-protein interaction networks. Through the generalization of an algorithm and a theoretical result about exclusion of minimum cuts, it was possible to reduce the number of maximum flow computations necessary to identify such complexes.

As opposed to public transit agencies' well-developed data generation capabilities, their utilization of their data is often overlooked. This study will tap into the potential of using the GTFS data format from an agency stakeholder perspective to assess transit performance. This format holds data for scheduled transit services, including real-time updates and network organization. The broad adaptation of GTFS by transit agencies (1240 transit networks in 672 locations worldwide) has made it a de-facto standard, making products built on top of it inherently scalable and could potentially be deployed in networks all over the world. The purpose of this thesis is two-fold; firstly, to explore how specific vulnerability features of nodes in a public transit network can be assessed using graph mining algorithms. Secondly, to develop a pipeline for aggregating GTFS data and fit it into a flow network model. The results include a data-driven framework for vulnerability characterization, a method for fitting GTFS data in a flow network model, and lastly, a definition for reduced flow capacity in a public transit context. Additionally, the results are presented in the setting of Uppsala's network (UL) and visualized with a web-based tool.

The master’s thesis focuses on the optimization models in logistics with emphasis on the network interdiction problem. The brief introduction is followed by two overview chapters - graph theory and mathematical programming. Important definitions strongly related to network interdiction problems are introduced in the chapter named Basic concepts of graph theory. Necessary theorems used for solving problems are following the definitions. Next chapter named Introduction to mathematical programming firstly contains concepts from linear programming. Definitions and theorems are chosen with respect to the following maximum flow problem and the derived dual problem. Concepts of stochastic optimization follow. In the fifth chapter, we discuss deterministic models of the network interdiction. Stochastic models of the network interdiction follow in the next chapter. All models are implemented in programmes written in the programming language GAMS, the codes are attached.