Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop Parameterized complexity became over last two decades one of the most impor- tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc- tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the tree-depth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the tree-width of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...

In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of: (1) a single cycle of length v, (2) f fixed points and a cycle of length v − f, or (3) two disjoint cycles. The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of Kv.

Soil conditions under vegetation cover and their spatial and temporal variations from point to catchment scale are crucial for understanding hydrological processes within the vadose zone, for managing irrigation and consequently maximizing yield by precision farming. Soil moisture and soil roughness are the key parameters that characterize the soil status. In order to monitor their spatial and temporal variability on large scales, remote sensing techniques are required. Therefore the determination of soil parameters under vegetation cover was approached in this thesis by means of (multi-angular) polarimetric SAR acquisitions at a longer wavelength (L-band, lambda=23cm). In this thesis, the penetration capabilities of L-band are combined with newly developed (multi-angular) polarimetric decomposition techniques to separate the different scattering contributions, which are occurring in vegetation and on ground. Subsequently the ground components are inverted to estimate the soil characteristics. The novel (multi-angular) polarimetric decomposition techniques for soil parameter retrieval are physically-based, computationally inexpensive and can be solved analytically without any a priori knowledge. Therefore they can be applied without test site calibration directly to agricultural areas. The developed algorithms are validated with fully polarimetric SAR data acquired by the airborne E-SAR sensor of the German Aerospace Center (DLR) for three different study areas in Germany. The achieved results reveal inversion rates up to 99% for the soil moisture and soil roughness retrieval in agricultural areas. However, in forested areas the inversion rate drops significantly for most of the algorithms, because the inversion in forests is invalid for the applied scattering models at L-band. The validation against simultaneously acquired field measurements indicates an estimation accuracy (root mean square error) of 5-10vol.% for the soil moisture (range of in situ values: 1-46vol.%) and of 0.37-0.45cm for the soil roughness (range of in situ values: 0.5-4.0cm) within the catchment. Hence, a continuous monitoring of soil parameters with the obtained precision, excluding frozen and snow covered conditions, is possible. Especially future, fully polarimetric, space-borne, long wavelength SAR missions can profit distinctively from the developed polarimetric decomposition techniques for separation of ground and volume contributions as well as for soil parameter retrieval on large spatial scales. / Zur Verbesserung der hydrologischen Abflussmodellierung, der Flutvorhersage, der gezielten Bewässerung von landwirtschaftlichen Nutzflächen und zum Schutz vor Ernteausfällen ist die Bestimmung der Bodenfeuchte und der Bodenrauhigkeit von grosser Bedeutung. Aufgrund der hohen zeitlichen sowie räumlichen Dynamik dieser Bodenparameter ist eine flächenhafte Erfassung mit hoher Auflösung und in kurzen zeitlichen Abständen notwendig. In situ Messtechniken stellen eine sehr zeit- und personalaufwändige Alternative dar, deshalb werden innovative Fernerkundungsverfahren mit aktivem Radar erprobt. Diese Aufnahmetechniken sind von Wetter- und Beleuchtungsverhältnissen unabhängig und besitzen zudem die Möglichkeit, abhängig von der Wellenlänge, in Medien einzudringen. Mit dem in dieser Arbeit verwendeten polarimetrischen Radar mit synthetischer Apertur (PolSAR) werden die Veränderungen der Polarisationen ausgewertet, da diese aufgrund der physikalischen Eigenschaften der reflektierenden Medien objektspezifisch verändert und gestreut werden. Es kann dadurch ein Bezug zwischen der empfangenen Radarwelle und den dielektrischen Eigenschaften (Feuchtegehalt) sowie der Oberflächengeometrie (Rauhigkeit) des Bodens hergestellt werden. Da vor allem in den gemässigten Klimazonen die landwirtschaftlichen Nutzflächen die meiste Zeit des Jahres mit Vegetation bestanden sind, wurden in dieser Dissertation Verfahren entwickelt, um die Bodenfeuchte und die Bodenrauhigkeit unter der Vegetation erfassen zu können. Um die einzelnen Rückstreubeiträge der Vegetation und des Bodens voneinander zu trennen, wurde die Eindringfähigkeit von längeren Wellenlängen (L-band, lambda=23cm) mit neu entwickelten (multi-angularen) polarimetrischen Dekompositionstechniken kombiniert, um die Komponente des Bodens zu extrahieren und auszuwerten. Für die Auswertung wurden polarimetrische Streumodelle benutzt, um die Bodenkomponente zu modellieren und dann mit der extrahierten Bodenkomponente der aufgenommenen Daten zu vergleichen. Die beste Übereinstimmung von Modell und Daten wurde als die gegebene Bodencharakteristik gewertet und dementsprechend invertiert. Die neu entwickelten, polarimetrischen Dekompositionstechniken für langwelliges polarimetrisches SAR basieren auf physikalischen Prinzipien, benötigen wenig Rechenzeit, erfordern keine Kalibrierung und sind ohne Verwendung von a priori Wissen analytisch lösbar. Um die entwickelten Algorithmen zu testen, wurden in drei verschiedenen Untersuchungsgebieten in Deutschland mit dem flugzeuggetragenen E-SAR Sensor des Deutschen Zentrums für Luft- und Raumfahrt (DLR) polarimetrische SAR Daten aufgenommen. Die Auswertungen der PolSAR Daten haben bestätigt, dass die besten Invertierungsergebnisse mit langen Wellenlängen erzielt werden können (L-Band). Des Weiteren konnten bei der Bestimmung der Bodenfeuchte und der Bodenrauhigkeit hohe Inversionsraten erreicht werden (bis zu 99% der Untersuchungsfläche). Es hat sich gezeigt, dass die polarimetrischen Streumodelle bei der gegebenen Wellenlänge nicht für bewaldete Gebiete geeignet sind, was die Anwendbarkeit des Verfahrens auf landwirtschaftliche Nutzflächen einschränkt. Die Validierung mit Bodenmessungen in den Untersuchungsgebieten, die zeitgleich zu den PolSAR Aufnahmen durchgeführt wurden, hat ergeben, dass eine kontinuierliche Beobachtung des Bodenzustandes (ausgenommen in Zeiten mit gefrorenem oder Schnee bedecktem Boden) mit einer Genauigkeit (Wurzel des mittleren quadratischen Fehlers) von 5-10vol.% für die Bodenfeuchte (in situ Messbereich: 1-46vol.%) und von 0.37-0.45cm für die Bodenrauhigkeit (in situ Messbereich: 0.5-4.0cm) möglich ist. Besonders künftige Fernerkundungsmissionen mit langwelligem, voll polarimetrischem SAR können von den entwickelten Dekompositionstechniken profitieren, um die Vegetationskomponente von der Bodenkomponente zu trennen und die Charakteristik des Oberbodens flächenhaft zu bestimmen.

In a typical orthogonal frequency division multiplexing (OFDM) broadband wireless communication system, a guard interval using cyclic prefix is inserted to avoid the inter-symbol interference and the inter-carrier interference. This guard interval is required to be at least equal to, or longer than the maximum channel delay spread. This method is very simple, but it reduces the transmission efficiency. This efficiency is very low in the communication systems, which inhibit a long channel delay spread with a small number of sub-carriers such as the IEEE 802.11a wireless LAN (WLAN). To increase the transmission efficiency, it is usual that a time domain equalizer (TEQ) is included in an OFDM system to shorten the effective channel impulse response within the guard interval. There are many TEQ algorithms developed for the low rate OFDM applications such as asymmetrical digital subscriber line (ADSL). The drawback of these algorithms is a high computational load. Most of the popular TEQ algorithms are not suitable for the IEEE 802.11a system, a high data rate wireless LAN based on the OFDM technique. In this thesis, a TEQ algorithm based on the minimum mean square error criterion is investigated for the high rate IEEE 802.11a system. This algorithm has a comparatively reduced computational complexity for practical use in the high data rate OFDM systems. In forming the model to design the TEQ, a reduced convolution matrix is exploited to lower the computational complexity. Mathematical analysis and simulation results are provided to show the validity and the advantages of the algorithm. In particular, it is shown that a high performance gain at a data rate of 54Mbps can be obtained with a moderate order of TEQ finite impulse response (FIR) filter. The algorithm is implemented in a field programmable gate array (FPGA). The characteristics and regularities between the elements in matrices are further exploited to reduce the hardware complexity in the matrix multiplication implementation. The optimum TEQ coefficients can be found in less than 4µs for the 7th order of the TEQ FIR filter. This time is the interval of an OFDM symbol in the IEEE 802.11a system. To compensate for the effective channel impulse response, a function block of 64-point radix-4 pipeline fast Fourier transform is implemented in FPGA to perform zero forcing equalization in frequency domain. The offsets between the hardware implementations and the mathematical calculations are provided and analyzed. The system performance loss introduced by the hardware implementation is also tested. Hardware implementation output and simulation results verify that the chips function properly and satisfy the requirements of the system running at a data rate of 54 Mbps.

In a typical orthogonal frequency division multiplexing (OFDM) broadband wireless communication system, a guard interval using cyclic prefix is inserted to avoid the inter-symbol interference and the inter-carrier interference. This guard interval is required to be at least equal to, or longer than the maximum channel delay spread. This method is very simple, but it reduces the transmission efficiency. This efficiency is very low in the communication systems, which inhibit a long channel delay spread with a small number of sub-carriers such as the IEEE 802.11a wireless LAN (WLAN). To increase the transmission efficiency, it is usual that a time domain equalizer (TEQ) is included in an OFDM system to shorten the effective channel impulse response within the guard interval. There are many TEQ algorithms developed for the low rate OFDM applications such as asymmetrical digital subscriber line (ADSL). The drawback of these algorithms is a high computational load. Most of the popular TEQ algorithms are not suitable for the IEEE 802.11a system, a high data rate wireless LAN based on the OFDM technique. In this thesis, a TEQ algorithm based on the minimum mean square error criterion is investigated for the high rate IEEE 802.11a system. This algorithm has a comparatively reduced computational complexity for practical use in the high data rate OFDM systems. In forming the model to design the TEQ, a reduced convolution matrix is exploited to lower the computational complexity. Mathematical analysis and simulation results are provided to show the validity and the advantages of the algorithm. In particular, it is shown that a high performance gain at a data rate of 54Mbps can be obtained with a moderate order of TEQ finite impulse response (FIR) filter. The algorithm is implemented in a field programmable gate array (FPGA). The characteristics and regularities between the elements in matrices are further exploited to reduce the hardware complexity in the matrix multiplication implementation. The optimum TEQ coefficients can be found in less than 4µs for the 7th order of the TEQ FIR filter. This time is the interval of an OFDM symbol in the IEEE 802.11a system. To compensate for the effective channel impulse response, a function block of 64-point radix-4 pipeline fast Fourier transform is implemented in FPGA to perform zero forcing equalization in frequency domain. The offsets between the hardware implementations and the mathematical calculations are provided and analyzed. The system performance loss introduced by the hardware implementation is also tested. Hardware implementation output and simulation results verify that the chips function properly and satisfy the requirements of the system running at a data rate of 54 Mbps.

A new two-dimensional transform is derived and implemented that is able to discriminate with respect to angular and radial frequency. This octave-band directional filter bank (OBDFB) is maximally decimated, has a separable polyphase implmentation, provides perfect reconstruction, and can be implemented in a tree structure allowing for a somewhat arbitrary number of angular and radial divisions. This decomposition is based on the directional filter bank (DFB) and is compared to other transforms with similar properties. Additionally, the OBDFB is used in three applications. Texture segmentation results are provided with comparisons to both decimated and undecimated transforms. With hyperspectral data, the OBDFB is used to increase classification accuracy using texture augmentation and likelihood score combination. Finally, ultrasound despeckling is addressed with respect to real-time implementations, and subjective test results are presented. A non-uniform two-dimensional transform is also designed that is a modified version of the OBDFB. It is rationally sampled and maximally decimated, but it provides both angular and radial frequency passbands from the initial stage instead of making separate divisions like the OBDFB. It also does not create subband boundaries on the principal frequency axes and allows for further decomposition as well.

Trade deficit, financial deficit, and current account deficit of the United States have all been problems deeply concerned by economists and politicians in recent decades. Since the third season of 2000, a recession of the United States and the whole world has gradually started to appear. In addition, as a result of the 9/11 terrorist attacks and the war in Iraq the stock market has begun to decline significantly. In order to promote the recovery of its economy, the federal government determines to adopt the expanded financial policy which will most likely in the end cause its financial deficit more serious. The main purpose of this paper is to investigate the factors that influence the current account deficit of the United States. Because the study considers foreign variables that related researches ignore, we choose five variables as follows: regional output differential, regional interest rate differential, terms of trade, regional real effective exchange rate, and current account. Therefore, we adopt the Unit Root Test, the Granger Causality Test, the Co-integrating Test, and SVAR (Structural Vector Autoregressive) model to run RATS and E-views. It is the finding of empirical result that the United States government considers terms of trade and current account that can't be quantized of the first importance rather than the exchange rate factor that general research is thought. This is one of the contributions of the study.

In this thesis, we define a new invariant of a Legendrian knot in a contact manifold using an open book decomposition supporting the contact structure. We define the support genus of a Legendrian knot L in a contact 3-manifold as the minimal genus of a page of an open book of M supporting the contact structure such that L sits on a page and the framings given by the contact structure and the page agree. For any topological link in 3-sphere we construct a planar open book decomposition whose monodromy is a product of positive Dehn twists such that the planar open book contains the link on its page. Using this, we show any topological link, in particular any knot in any 3-manifold M sits on a page of a planar open book decomposition of M and we show any null-homologous loose Legendrian knot in an overtwisted contact structure has support genus zero.

In this thesis, we write explicitly the open book decompositions of links of quotient surface singularities that support the corresponding unique Milnor fillable contact structures. The page-genus of these Milnor open books are minimal among all Milnor open books supporting the corresponding unique Milnor fillable contact structures. That minimal page-genus is called Milnor genus. In this thesis we also investigate whether the Milnor genus is equal to the support genus for links of quotient surface singularities. We show that for many types of the quotient surface singularities the Milnor genus is equal to the support genus of the corresponding contact structure. For the remaining we are able to find an upper bound for the support genus which would be a step forward in understanding these contact structures.

This dissertation is on a study of 2-string free tangle decompositions of knots with tunnel number two. As an application, we construct infinitely many counter-examples to a conjecture in the literature stating that the tunnel number of the connected sum of prime knots doesn't degenerate by more than one: t(K_1#K_2)≥ t(K_1)+t(K_2)-1, for K_1 and K_2 prime knots. We also study 2-string free tangle decompositions of links with tunnel number two and obtain an equivalent statement to the one on knots. Further observations on tunnel number and essential tangle decompositions are also made. / text