No / We present an explicit polynomial solution method for surface generation. In this case the surface in question is characterized by some boundary configuration whereby the resulting surface conforms to a fourth order linear elliptic Partial Differential Equation, the Euler–Lagrange equation of a quadratic functional defined by a norm. In particular, the paper deals with surfaces generated as explicit Bézier polynomial solutions for the chosen Partial Differential Equation. To present the explicit solution methodologies adopted here we divide the Partial Differential Equations into two groups namely the orthogonal and the non-orthogonal cases. In order to demonstrate our methodology we discuss a series of examples which utilize the explicit solutions to generate smooth surfaces that interpolate a given boundary configuration. We compare the speed of our explicit solution scheme with the solution arising from directly solving the associated linear system.

Neste trabalho investigamos, dos pontos de vistas analítico e numérico, o comportamento assintótico da solução da equação do aerofólio, com uma singularidade do tipo Cauchy, de nida sobre um intervalo com uma pequena abertura. Exibimos um modelo matemático com uma solução f" para o intervalo disjunto G" = (−1,−ε) ∪ (ε, 1) e uma solução f0 que corresponde ao limite de f" quando (ε → 0), relacionando esta última com a solução da equação do aerofólio f no intervalo (−1, 1). Além do mais, demonstramos casos particulares de funções ψ = Tm e ψ = Un(onde Tm e Un são os polinômios de Tchebychev do primeiro e segundo tipo respectivamente) em que temos a igualdade f = f0 e conseqüentemente f" ≈ f. Apresentamos e comparamos numericamente as soluções f", f0 e f para diferentes funções ψ e valores de ε no intervalo G". Mostramos ainda soluções quase polinomiais analíticas da equação do aerofólio, e propomos um método espectral para a equação do aerofólio generalizada. Por m, obtemos soluções analíticas das equações do aerofólio para os intervalos G", (−1, 1)\ {0} e (−1, 1) para diferentes funções ψ(t) através da expansão em série da densidade da integral singular com núcleo Cauchy. / In this work we investigate, of the analytical and numerical points of views, the asymptotic behavior of the airfoil equation solution with a singularity of the Cauchy type, de ned over a interval with a small opening. We display a mathematical model with a f" solution to the disjoint interval G" = (−1,−ε)∪(ε, 1) and a f0 solution corresponding to limit of f" when (ε → 0), linking the latter with the solution of the airfoil equation f in the interval (−1, 1). Furthermore, we demonstrate particular cases of functions ψ = Tm and ψ = Un (where Tm and Un are the Chebyshev polynomials of the rst and second type respectively) where we have equality f = f0 and then f" ≈ f. We present and compare numerically the solutions f", f0 and f for di erent functions ψ and values of ε in G". We also show almost polynomial analytical solutions for the airfoil equation, and we propose a spectral method for the generalized airfoil equation. Finally, we obtain analytical solutions of the airfoil equations to the interval G", (−1, 1)\ {0} and (−1, 1) for various functions ψ(t) by expanding in series the density of the Cauchy singular integral.

Neste trabalho investigamos, dos pontos de vistas analítico e numérico, o comportamento assintótico da solução da equação do aerofólio, com uma singularidade do tipo Cauchy, de nida sobre um intervalo com uma pequena abertura. Exibimos um modelo matemático com uma solução f" para o intervalo disjunto G" = (−1,−ε) ∪ (ε, 1) e uma solução f0 que corresponde ao limite de f" quando (ε → 0), relacionando esta última com a solução da equação do aerofólio f no intervalo (−1, 1). Além do mais, demonstramos casos particulares de funções ψ = Tm e ψ = Un(onde Tm e Un são os polinômios de Tchebychev do primeiro e segundo tipo respectivamente) em que temos a igualdade f = f0 e conseqüentemente f" ≈ f. Apresentamos e comparamos numericamente as soluções f", f0 e f para diferentes funções ψ e valores de ε no intervalo G". Mostramos ainda soluções quase polinomiais analíticas da equação do aerofólio, e propomos um método espectral para a equação do aerofólio generalizada. Por m, obtemos soluções analíticas das equações do aerofólio para os intervalos G", (−1, 1)\ {0} e (−1, 1) para diferentes funções ψ(t) através da expansão em série da densidade da integral singular com núcleo Cauchy. / In this work we investigate, of the analytical and numerical points of views, the asymptotic behavior of the airfoil equation solution with a singularity of the Cauchy type, de ned over a interval with a small opening. We display a mathematical model with a f" solution to the disjoint interval G" = (−1,−ε)∪(ε, 1) and a f0 solution corresponding to limit of f" when (ε → 0), linking the latter with the solution of the airfoil equation f in the interval (−1, 1). Furthermore, we demonstrate particular cases of functions ψ = Tm and ψ = Un (where Tm and Un are the Chebyshev polynomials of the rst and second type respectively) where we have equality f = f0 and then f" ≈ f. We present and compare numerically the solutions f", f0 and f for di erent functions ψ and values of ε in G". We also show almost polynomial analytical solutions for the airfoil equation, and we propose a spectral method for the generalized airfoil equation. Finally, we obtain analytical solutions of the airfoil equations to the interval G", (−1, 1)\ {0} and (−1, 1) for various functions ψ(t) by expanding in series the density of the Cauchy singular integral.

Neste trabalho investigamos, dos pontos de vistas analítico e numérico, o comportamento assintótico da solução da equação do aerofólio, com uma singularidade do tipo Cauchy, de nida sobre um intervalo com uma pequena abertura. Exibimos um modelo matemático com uma solução f" para o intervalo disjunto G" = (−1,−ε) ∪ (ε, 1) e uma solução f0 que corresponde ao limite de f" quando (ε → 0), relacionando esta última com a solução da equação do aerofólio f no intervalo (−1, 1). Além do mais, demonstramos casos particulares de funções ψ = Tm e ψ = Un(onde Tm e Un são os polinômios de Tchebychev do primeiro e segundo tipo respectivamente) em que temos a igualdade f = f0 e conseqüentemente f" ≈ f. Apresentamos e comparamos numericamente as soluções f", f0 e f para diferentes funções ψ e valores de ε no intervalo G". Mostramos ainda soluções quase polinomiais analíticas da equação do aerofólio, e propomos um método espectral para a equação do aerofólio generalizada. Por m, obtemos soluções analíticas das equações do aerofólio para os intervalos G", (−1, 1)\ {0} e (−1, 1) para diferentes funções ψ(t) através da expansão em série da densidade da integral singular com núcleo Cauchy. / In this work we investigate, of the analytical and numerical points of views, the asymptotic behavior of the airfoil equation solution with a singularity of the Cauchy type, de ned over a interval with a small opening. We display a mathematical model with a f" solution to the disjoint interval G" = (−1,−ε)∪(ε, 1) and a f0 solution corresponding to limit of f" when (ε → 0), linking the latter with the solution of the airfoil equation f in the interval (−1, 1). Furthermore, we demonstrate particular cases of functions ψ = Tm and ψ = Un (where Tm and Un are the Chebyshev polynomials of the rst and second type respectively) where we have equality f = f0 and then f" ≈ f. We present and compare numerically the solutions f", f0 and f for di erent functions ψ and values of ε in G". We also show almost polynomial analytical solutions for the airfoil equation, and we propose a spectral method for the generalized airfoil equation. Finally, we obtain analytical solutions of the airfoil equations to the interval G", (−1, 1)\ {0} and (−1, 1) for various functions ψ(t) by expanding in series the density of the Cauchy singular integral.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.