In (J Graph Theory 33 (2000), 14-24), Hell and Zhu proved that if a series-parallel graph G has girth at least 2⌊(3k-1)/2⌋, then χc(G)≤4k/(2k-1). In (J Graph Theory 33 (2000), 185-198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14-24) is sharp. Short proofs of both results are given in this note.

Many parallel programming languages allow programmers to describe parallelism by using constructs such as fork/join. When executed, such programs can be modeled as directed graphs, with nodes representing a computation and edges representing the sequence and dependency. However, because it does not coerce regularity in the computation, the general model is not amenable to efficient execution of the resulting program. Therefore, a more restrictive model called Series-Parallel DAG (Directed Acyclic Graph) has been proposed and adopted by several major parallel languages. As reported by the Cilk developers, many parallel computations can be easily expressed in the series-parallel model, and there are provably efficient scheduling algorithms for the SP DAGs. Nevertheless, it remains open how much inherent parallelism will be lost when conforming to the model, because expressing a computation in the series-parallel model may also induce performance losses. We will show that any general DAG can be converted into an SP DAG without violating the original precedence relations; moreover, the conversion can be carried out in essentially linear time and space, and the resulting DAG exhibits little loss in the parallelism. Since the resulting SP DAG can then be executed with high efficiency, it implies that the languages based on SP DAGs are not as restrictive as they were thought to be. / Singapore-MIT Alliance (SMA)

Title: Flows and cuts with constraints Author: Dušan Knop Department: Department of applied mathematics Supervisor: Doc. Mgr. Petr Kolman, PhD, Department of applied mathematics Abstract: In this thesis we study the problem of length bounded cuts between two vertices of a graph. In this problem the task is to find a set of edges such that after its removal the minimal distance between the two vertices is as prescribed. The work provides a basic overview of the literature on this problem and presents it in the context of other theoretical problems. It also offers some applications of length bounded cuts and flows. We describe some heuristics for data reduction. The main result of this thesis is a polynomial time algorithm in series-parallel graphs for problem of length bounded cut, which is NP-hard in general. Keywords: cuts, series-parallel graphs, algorithm, complexity

A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of perfect matchings in a bipartite graph. We focus on the problem of counting the common bases in pairs of regular matroids, and describe a class called <i>Pfaffian matroid pairs</i> for which this enumeration problem can be solved. We prove that when a pair of regular matroids is non-Pfaffian, there is a set of common bases which certifies this, and that the number of bases in the certificate is linear in the size of the ground set of the matroids. When both matroids in a pair are series-parallel, we prove that determining if the pair is Pfaffian is equivalent to finding an edge signing in an associated graph, and in the case that the pair is non-Pfaffian, we obtain a characterization of this associated graph. Pfaffian bipartite graphs are a class of graphs for which the number of perfect matchings can be determined; we show that the class of series-parallel Pfaffian matroid pairs is an extension of the class of Pfaffian bipartite graphs. Edmonds proved that the polytope generated by the common bases of a pair of matroids is equal to the intersection of the polytopes generated by the bases for each matroid in the pair. We consider when a similar property holds for the binary space, and give an excluded minor characterization of when the binary space generated by the common bases of two matroids can not be determined from the binary spaces for the individual matroids. As a result towards a description of the lattice of common bases for a pair of matroids, we show that the lattices for the individual matroids determine when all common bases of a pair of matroids intersect a subset of the ground set with fixed cardinality.

A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of perfect matchings in a bipartite graph. We focus on the problem of counting the common bases in pairs of regular matroids, and describe a class called <i>Pfaffian matroid pairs</i> for which this enumeration problem can be solved. We prove that when a pair of regular matroids is non-Pfaffian, there is a set of common bases which certifies this, and that the number of bases in the certificate is linear in the size of the ground set of the matroids. When both matroids in a pair are series-parallel, we prove that determining if the pair is Pfaffian is equivalent to finding an edge signing in an associated graph, and in the case that the pair is non-Pfaffian, we obtain a characterization of this associated graph. Pfaffian bipartite graphs are a class of graphs for which the number of perfect matchings can be determined; we show that the class of series-parallel Pfaffian matroid pairs is an extension of the class of Pfaffian bipartite graphs. Edmonds proved that the polytope generated by the common bases of a pair of matroids is equal to the intersection of the polytopes generated by the bases for each matroid in the pair. We consider when a similar property holds for the binary space, and give an excluded minor characterization of when the binary space generated by the common bases of two matroids can not be determined from the binary spaces for the individual matroids. As a result towards a description of the lattice of common bases for a pair of matroids, we show that the lattices for the individual matroids determine when all common bases of a pair of matroids intersect a subset of the ground set with fixed cardinality.

No description available.

Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G = (V, E) is a non empty set S ⊆ V where, for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc [Sha01, FLG00, SX07]. In [GK98, GK00], Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the "Satisfactory Graph Partitioning (SGP)" problem. In his dissertation , Shafique used the problem of partitioning a graph into alliances to model problems in data clustering. Decision problems for several types of alliances and alliance partitions have been shown to be NP-complete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in [DF99]. In addition to parameterized algorithms for alliance related problems, we study the partition of series-parallel graphs into alliances. The class of series-parallel graphs is a special class in graph theory since many problems known to be NP-complete on general graphs have been shown to have polynomial time algorithms on series-parallel graphs [ZLL04, Hoj95, DS99, HHL87, TNS82]. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to series-parallel graphs . Series-parallel graphs have also been to focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning series-parallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of series-parallel graphs that allow a partition into defensive alliances and a subclass of series-parallel graphs with a satisfactory partitions.

No description available.

Yes / This paper presents a study on selective maintenance for multi-state series-parallel systems with economically dependent components. In the selective maintenance problem, the maintenance manager has to decide which components should receive maintenance activities within a finite break between missions. All the system reliabilities in the next operating mission, the available budget and the maintenance time for each component from its current state to a higher state are taken into account in the optimization models. In addition, the components in series-parallel systems are considered to be economically dependent. Time and cost savings will be achieved when several components are simultaneously repaired in a selective maintenance strategy. As the number of repaired components increases, the saved time and cost will also increase due to the share of setting up between components and another additional reduction amount resulting from the repair of multiple identical components. Different optimization models are derived to find the best maintenance strategy for multi-state series-parallel systems. A genetic algorithm is used to solve the optimization models. The decision makers may select different components to be repaired to different working states based on the maintenance objective, resource availabilities and how dependent the repair time and cost of each component are. © 2013 Elsevier Ltd. All rights reserved. / Natural Sciences and Engineering Research Council of Canada (NSERC) and Vietnam International Education Development (VIED)

Recentemente os sistemas de transferência de energia sem fio WPT (do inglês Wireless Power Transfer) têm sido amplamente estudados com o propósito de alimentar eficientemente diversos tipos de cargas através de técnicas específicas, dentre elas destaca-se a transferência capacitiva de potência CPT (do inglês Capacitive Power Transfer) e a transferência indutiva de potência IPT (do inglês Inductive Power Transfer), sendo esta última objeto deste estudo. Em um sistema de transferência indutiva de potência a carga é alimentada através de um transformador fracamente acoplado. Em função do elevado espaçamento entre as bobinas primária e secundária, da ausência de núcleo magnético, ou o emprego do núcleos divididos e separados por um grande entreferro, o transformador apresenta alta reatância de dispersão e baixa reatância de magnetização, o que resulta em elevadas correntes, baixa eficiência e regulação da tensão ruim quando houver variação da carga. Com o intuito de aumentar a eficiência e melhorar a regulação de tensão (ou corrente) são aplicadas compensações capacitivas em ambos os lados do transformador, elevando o número de elementos reativos, o que dificulta a compreensão do seu comportamento. Adicionalmente, as diversas configurações geométricas possíveis para a construção das bobinas dificultam a otimização do projeto de transferência indutiva de potência. Esta dissertação analisa e compara as estratégias de compensação série-série (SS) e série-paralela (SP) sob diversos pontos de vista, identificando pontos de operação relevantes nos quais o sistema atua como uma fonte de corrente ou de tensão em malha aberta, modela os elementos que constituem um sistema de transferência indutiva de potência para alcançar à eficiência requisitada. Adicionalmente este trabalho lista os impactos na fonte e na carga quando do desvio das condições nominais de operação e dá diretrizes que permitem escolher os elementos de um sistema IPT. Na sequência esta dissertação propõe as diretrizes para a construção do transformador com valores predefinidos de fator de qualidade, indutâncias próprias e fator de acoplamento. Por fim, o presente trabalho dimensiona e confecciona alguns sistemas IPT a partir de uma lista de especificações, usando uma metodologia de projeto baseada em fórmulas aproximadas e a valida experimentalmente. / Recently Wireless Power Transfer (WPT) is widely studied in order to efficiently feed many different kinds of loads using specific techniques, such as Capacitive Power Transfer (CPT) and Inductive Power Transfer (IPT). IPT system relies on large air gap and loosely coupled transformer which will be studied in this work. Due to the large separation between the primary and secondary coils, the absence of a magnetic core, or the presence of split cores the transformer presents large leakage inductances, resulting in poor voltage regulation against load variation. Moreover, the low magnetizing inductance results in high magnetizing currents, reducing the overall efficiency. In order to improve the WPT performance, capacitive compensation techniques are applied in both sides of the transformer. Series compensation is commonly used at the primary side of the WPT transformer while Series or Parallel compensation is eligible to the secondary side. In addition, the loosely coupled transformer must be designed, in spite of the complex relationship between the various electrical and geometrical parameters of the coils that complicates the transformer construction and its optimization. This work compares Series-Series and Series-Parallel compensation strategies based on a simple approach, comprehensively highlighting the pro and cons of each one. Also the open loop operation in voltage source and current source modes, and the effect of the gap length for both compensation strategies are discussed. Moreover, the elements that constitute an inductive power transfer system are modeled in order to achieve the required efficiency. This research also proposes some guidance to build the transformer with high figure-of-merit and coupling. Finally, the present work designs and builds few IPT systems that satisfies a set of specifications, based on a simplified design procedure. The proposed design methodology is experimentally validated.