On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Two-dimensional Cartesian air-gap element (CAGE) for dynamic finite-element modeling of electrical machines with a flat air gap

This paper extends the air-gap element (AGE) to enable the modeling of flat air gaps. AGE is a macroelement originally proposed by Abdel-Razek et al.for modeling annular air gaps in electrical machines. The paper presents the theory of the new macroelement and explains its implementation within a time-stepped finite-element (FE) code. It validates the solution produced by the new macroelement by comparing it with that obtained by using an FE mesh with a discretized air gap. It then applies the model to determine the open-circuit electromotive force of an axial-flux permanent-magnet machine and compares the results with measurements.

A general design method for electric machines using magnetic circuit model considering the flux saturation problem

This paper proposes an analytical approach that is generalized for the design of various types of electric machines based on a physical magnetic circuit model. Conventional approaches have been used to predict the behavior of electric machines but have limitations in accurate flux saturation analysis and hence machine dimensioning at the initial design stage. In particular, magnetic saturation is generally ignored or compensated by correction factors in simplified models since it is difficult to determine the flux in each stator tooth for machines with any slot-pole combinations. In this paper, the flux produced by stator winding currents can be calculated accurately and rapidly for each stator tooth using the developed model, taking saturation into account. This aids machine dimensioning without the need for a computationally expensive finite element analysis (FEA). A 48-slot machine operated in induction and doubly-fed modes is used to demonstrate the proposed model. FEA is employed for verification.

A robust position control for induction machines

ICEM 2010