The current Internet architecture presents a barrier to accommodate the vigorous arising demand for deploying new network services and applications. The next-generation architecture views the network virtualization as the gateway to overcome this limitation. Network virtualization promises to run efficiently and securely multiple dedicated virtual networks (VNs) over a shared physical infrastructure. Each VN is tailored to host a unique application based on the user’s preferences. This thesis addresses the problem of the efficient embedding of multiple VNs onto a shared substrate network (SN). The contribution of this thesis are twofold: First, a novel hierarchical SN management framework is proposed that efficiently selects the optimum VN mapping scheme for the requested VN from more than one proposed VN mapping candidates obtained in parallel. In order to accommodate the arbitrary architecture of the VNs, the proposed scheme divides the VN request into smaller subgraphs, and individually maps them on the SN using a variation of the exact subgraph matching techniques. Second, the physical resources pricing policy is introduced that is based on time-ofuse, that reflects the effect of resource congestion introduced by VN users. The preferences of the VN users are first represented through corresponding demand-utility functions that quantify the sensitivity of the applications hosted by the VNs to resource consumption and time-of-use. A novel model of time-varying VNs is presented, where users are allowed to up- or down-scale the requested resources to continuously maximize their utility while minimizing the VNs embedding cost. In contrast to existing solutions, the proposed work does not impose any limitations on the size or topology of the VN requests. Instead, the search is customized according to the VN size and the associated utility. Extensive simulations are then conducted to demonstrate the improvement achieved through the proposed work in terms of network utilization, the ratio of accepted VN requests and the SP profits.

In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph. TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution. For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3. For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.

Genes can be associated in numerous ways, e.g. by co-expression in micro-arrays, co-regulation in operons and regulons or co-localization on the genome. Association of genes often indicates that they contribute to a common biological function, such as a pathway. The aim of this thesis is to predict metabolic pathways from associated enzyme-coding genes. The prediction approach developed in this work consists of two steps: First, the reactions are obtained that are carried out by the enzymes coded by the genes. Second, the gaps between these seed reactions are filled with intermediate compounds and reactions. In order to select these intermediates, metabolic data is needed. This work made use of metabolic data collected from the two major metabolic databases, KEGG and MetaCyc. The metabolic data is represented as a network (or graph) consisting of reaction nodes and compound nodes. Interme- diate compounds and reactions are then predicted by connecting the seed reactions obtained from the query genes in this metabolic network using a graph algorithm.<p>In large metabolic networks, there are numerous ways to connect the seed reactions. The main problem of the graph-based prediction approach is to differentiate biochemically valid connections from others. Metabolic networks contain hub compounds, which are involved in a large number of reactions, such as ATP, NADPH, H2O or CO2. When a graph algorithm traverses the metabolic network via these hub compounds, the resulting metabolic pathway is often biochemically invalid.<p>In the first step of the thesis, an already existing approach to predict pathways from two seeds was improved. In the previous approach, the metabolic network was weighted to penalize hub compounds and an extensive evaluation was performed, which showed that the weighted network yielded higher prediction accuracies than either a raw or filtered network (where hub compounds are removed). In the improved approach, hub compounds are avoided using reaction-specific side/main compound an- notations from KEGG RPAIR. As an evaluation showed, this approach in combination with weights increases prediction accuracy with respect to the weighted, filtered and raw network.<p>In the second step of the thesis, path finding between two seeds was extended to pathway prediction given multiple seeds. Several multiple-seed pathay prediction approaches were evaluated, namely three Steiner tree solving heuristics and a random-walk based algorithm called kWalks. The evaluation showed that a combination of kWalks with a Steiner tree heuristic applied to a weighted graph yielded the highest prediction accuracy.<p>Finally, the best perfoming algorithm was applied to a microarray data set, which measured gene expression in S. cerevisiae cells growing on 21 different compounds as sole nitrogen source. For 20 nitrogen sources, gene groups were obtained that were significantly over-expressed or suppressed with respect to urea as reference nitrogen source. For each of these 40 gene groups, a metabolic pathway was predicted that represents the part of metabolism up- or down-regulated in the presence of the investigated nitrogen source.<p>The graph-based prediction of pathways is not restricted to metabolic networks. It may be applied to any biological network and to any data set yielding groups of associated genes, enzymes or compounds. Thus, multiple-end pathway prediction can serve to interpret various high-throughput data sets. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The current Internet architecture presents a barrier to accommodate the vigorous arising demand for deploying new network services and applications. The next-generation architecture views the network virtualization as the gateway to overcome this limitation. Network virtualization promises to run efficiently and securely multiple dedicated virtual networks (VNs) over a shared physical infrastructure. Each VN is tailored to host a unique application based on the user’s preferences. This thesis addresses the problem of the efficient embedding of multiple VNs onto a shared substrate network (SN). The contribution of this thesis are twofold: First, a novel hierarchical SN management framework is proposed that efficiently selects the optimum VN mapping scheme for the requested VN from more than one proposed VN mapping candidates obtained in parallel. In order to accommodate the arbitrary architecture of the VNs, the proposed scheme divides the VN request into smaller subgraphs, and individually maps them on the SN using a variation of the exact subgraph matching techniques. Second, the physical resources pricing policy is introduced that is based on time-ofuse, that reflects the effect of resource congestion introduced by VN users. The preferences of the VN users are first represented through corresponding demand-utility functions that quantify the sensitivity of the applications hosted by the VNs to resource consumption and time-of-use. A novel model of time-varying VNs is presented, where users are allowed to up- or down-scale the requested resources to continuously maximize their utility while minimizing the VNs embedding cost. In contrast to existing solutions, the proposed work does not impose any limitations on the size or topology of the VN requests. Instead, the search is customized according to the VN size and the associated utility. Extensive simulations are then conducted to demonstrate the improvement achieved through the proposed work in terms of network utilization, the ratio of accepted VN requests and the SP profits.

In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph. TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution. For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3. For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24730号 / 情博第818号 / 新制||情||138(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 阿久津 達也, 教授 山本 章博, 教授 岡部 寿男 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Determining the chromatic number of the partition graph P(33) poses a considerable challenge. We can bound it to 4 ≤ χ(P(33)) ≤ 6, with exhaustive search confirming χ(P(33)) = 6. A potential mathematical proof strategy for this equality involves identifying a Z2-invariant S4 with non-trivial homology in the box complex of the partition graph P(33), namely Bedge(︁P(33))︁, and applying the Borsuk-Ulam theorem to compute its Z2-index. This provides a robust topological lower bound for the chromatic number of P(33), termed the Lovász bound. We have verified the absence of such an S4 within certain sections of Bedge(︁P(33))︁. We also validated this approach through a case study on the Petersen graph. This thesis offers a thorough examination of various topological lower bounds for a graph’s chromatic number, complete with proofs and examples. We demonstrate instances where these lower bounds converge to a single value and others where they diverge significantly from a graph’s actual chromatic number. We also classify all vertex pairs, triples, and quadruples of P(33) into unique equivalence classes, facilitating the derivation of all maximal complete bipartite subgraphs. This classification informs the construction of all simplices of Bedge(︁P(33)). Following a detailed and technical exploration, we uncover both the maximal size of the pairwise intersections of its maximal simplices and their underlying structure. Our study proposes an algorithm for building the box complex of the partition graph P(33) using our method of identifying maximal complete bipartite subgraphs. This reduces time complexity to O(n3), marking a substantial enhancement over brute-force techniques. Lastly, we apply discrete Morse theory to construct a simplicial complex homotopy equivalent to the box complex of P(33), using two methods: elementary collapses and the determination of a discrete Morse function on the box complex. This process reduces the dimension of the box complex from 35 to 12, streamlining future calculations of the Z2-index and the Lovász bound.

No description available.

No description available.

Software forking---creating a variant product by copying and modifying an existing project---is often considered an ad hoc, low cost alternative to principled product line development. To maintain forked projects, developers need to manually port existing features or bug-fixes from one project to another. Such manual porting is not only tedious but also error-prone. When the contexts of the ported code vary, developers often have to adapt the ported code to fit its surroundings. Faulty adaptations or inconsistent updates of the ported code could potentially introduce subtle inconsistencies in the codebase. To build a deeper understanding to cross-system porting and porting related errors, this dissertation investigates: (1) How can we identify ported code from software version histories? (2) What is the overhead of cross-system porting required to maintain forked projects? (3) What is the extent and characteristics of porting errors that occur in practice? and (4) How can we detect and characterize potential porting errors? As a first step towards assessing the overhead of cross-system porting, we implement REPERTOIRE, a tool to analyze repeated work of cross-system porting across peer projects. REPERTOIRE can detect ported edits between program patches with high accuracy of 94% precision and 84% recall. Using REPERTOIRE, we study the temporal, spatial, and developer dimensions of cross-system porting using 18 years of parallel evolution history of the BSD product family. Our study finds that cross-system porting happens periodically and the porting rate does not necessarily decrease over time. The upkeep work of porting changes from peer projects is significant and currently, porting practice seems to heavily depend on developers doing their porting job on time. Analyzing version histories of Linux and FreeBSD, we derive five categories of porting errors, including incorrect control- and data-flow, code redundancy, and inconsistent identifier and token renamings. Leveraging this categorization, we design a static control- and data-dependence analysis technique, SPA, to detect and characterize porting inconsistencies. SPA detects porting inconsistencies with 65% to 73% precision and 90% recall, and identify inconsistency types with 58% to 63% precision and 92% recall on average. In a comparison with two existing error detection tools, SPA outperforms them with 14% to 17% better precision. / text