Search

Given a graph G, we define bcg (G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γ k . A graph class G has the SQGC property if every graph G ∈ G has treewidth O (bcg (G) c) for some 1 ≤ c < 2 . The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQGC property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems. [ABSTRACT FROM AUTHOR]

Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work. [ABSTRACT FROM AUTHOR]

Many algorithms have been developed for NP-hard problems on graphs with small treewidth k . For example, all problems that are expressible in linear extended monadic second order can be solved in linear time on graphs of bounded treewidth. It turns out that the bottleneck of many algorithms for NP-hard problems is the computation of a tree decomposition of width O ( k ) . In particular, by the bidimensional theory, there are many linear extended monadic second order problems that can be solved on n -vertex planar graphs with treewidth k in a time linear in n and subexponential in k if a tree decomposition of width O ( k ) can be found in such a time. We present the first algorithm that, on n -vertex planar graphs with treewidth k , finds a tree decomposition of width O ( k ) in such a time. In more detail, our algorithm has a running time of O ( n k 2 log ⁡ k ) . We show the result as a special case of a result concerning so-called weighted treewidth of weighted graphs. [ABSTRACT FROM AUTHOR]

Interferometric synthetic aperture radar (InSAR) is a phase-based radar signal processing technique that has been addressed from a polarimetric point of view since the late 1990s, starting with Cloude and Papathanassiou's foundational work. Polarimeric InSAR (PolInSAR) has consolidated as an active field of research in parallel to non-PolInSAR. Regarding the latter, there have been a number of issues that were discussed in an earlier paper from which some other questions related to Cloude's PolInSAR come out naturally. In particular, they affect the usual understanding of coherence and statistical independence. Coherence involves the behavior of electromagnetic waves in at least a pair of points, and it is crucially related to the statistical independence of scatterers in a complex scene. Although this would seem to allow PolInSAR to overcome the difficulties involving the controversial confusion between statistical independence and polarization as present in PolSAR, Cloude's PolInSAR originally inherited the idea of separating physical contributors to the scattering phenomenon through the use of singular values and vectors. This was an assumption consistent with Cloude's PolSAR postulates that was later set aside. We propose the introduction of a multidimensional coherence tensor that includes PolInSAR's polarimetric interferometry matrix Ω12 as its 2-D case. We show that some important properties of the polarimetric interferometry matrix are incidental to its bidimensionality. Notably, this exceptional behavior in 2-D seems to suggest that the singular value decomposition (SVD) of Ω12 does not provide a physical insight into the scattering problem in the sense of splitting different scattering contributors. It might be argued that Cloude's PolInSAR in its current form does not rely on the SVD of Ω12 but on other underlying optimization schemes. The drawbacks of such ulterior developments and the failure of the maximum coherence separation procedure to be a consistent scheme for surface topography estimation in a two-layer model are discussed in depth in this paper. Nevertheless, turning back to the SVD of Ω12, the use of the singular values of a prewhitened version of Ω12 is consistent with a leading method of characterizing coherence in modern Optics. For this reason, the utility of the SVD of Ω12 as a means of characterizing coherence is analyzed here and extended to higher dimensionalities. Finally, these extensions of the concept of coherence to the multidimensional case are tested and compared with the 2-D case by numerically simulating the scattered electromagnetic field from a rough surface. [ABSTRACT FROM PUBLISHER]

From a reading of Sein und Zeit and contemporary courses, we are interested in examining the transcendental structure of Dasein to explain what we understand as its bidimensional character. For this, we analyze the function of the mood in the dynamics of the structure through the anxiety (Angst) and profound boredom (tiefe Langeweile). We emphasize the affective disposition as an existential starting point and condition of possibility for two pathways, since in relation to being we observed tension between two dimensions that are oscillated Dasein towards one concealment and one unconcealed motion of what happens. With this interpretation we intend to show that the tensive dynamics of the bidimensional structure of Dasein proposed here is the effect of the original givenness of being. [ABSTRACT FROM AUTHOR]

From a reading of Sein und Zeit and contemporary courses, we are interested in examining the transcendental structure of Dasein to explain what we understand as its bidimensional character. For this, we analyze the function of the mood in the dynamics of the structure through the anxiety (Angst) and profound boredom (tiefe Langeweile). We emphasize the affective disposition as an existential starting point and condition of possibility for two pathways, since in relation to being we observed tension between two dimensions that are oscillated Dasein towards one concealment and one unconcealed motion of what happens. With this interpretation we intend to show that the tensive dynamics of the bidimensional structure of Dasein proposed here is the effect of the original givenness of being. [ABSTRACT FROM AUTHOR]

Abstract: We provide two parameterized graphs , with the following property: for every positive integer k, there is a constant such that every graph G with treewidth at least , contains one of , , as a contraction, where is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences. [Copyright &y& Elsevier]

The psychoanalytical literature has numerous scattered references to the analyst’s experience of boredom, especially amongst writers working with primitive mental states. In the present paper, the author tries to gather some of these references in an attempt to integrate the various facets of this widespread phenomenon, and reflect on some clinical issues and dilemmas it raises. It is suggested that the experience of boredom in analysis may be a reaction to an encounter with a hidden, encapsulated part of the psyche, a bidimensional area of experience in which mental activity has been suspended, and experience remains meaningless. This is a barren area of lack, an encounter with the autistic core of the psyche. However, boredom may also be an experiential expression of despair, a re-living of primitive object relations with an emotionally non-existent primary object. Through bringing the emptiness and desolation into analysis, the individual makes room for the empty, blunt, dead inner object which resides within him, and that needs to be integrated into the psyche. This inner object is a vital part of the patient’s inner world, part of his history, and can neither be erased nor filled in order to eradicate the emptiness. This is illustrated by clinical material from patients along the spectrum of autism, autistic reaction following trauma and autistic barriers in neurotic patients. [ABSTRACT FROM AUTHOR]

Abstract: The status of the first invested object at the beginning of psychic life is a complex, scientific, philosophical as well as human enigma. The authors have a vision that is both personal and inspired by the broad metapsychological field and this field has usually been used for a descriptive or even explanatory support for inquiry. The support of their vision is based on a three-part concept, which brings together pictographic representation processes in the sense of “containing”, the reflecting role of the external object and bidimensionality. Their modeling describes the primary object in the form of a psychological experience of nondifferentiation between the constantly evolving subject and his environment, initiated with an originating framework at the beginning of life, which then gradually becomes, and in a way that varies with the individual, the ultimate primary trace. [Copyright &y& Elsevier]

A series of hybrid electrode materials, poly(3,4-ethylenedioxythiophene)/V2O5, has been synthesized using an oxidative insertion and polymerization reaction. FTIR, X-ray diffraction and transmission electron microscopy studies have shown that the incorporation of polymer between V2O5 slabs leads to an enhanced bidimensionality. The electrochemical lithium capacity has been increased up to ∼330 mAh/g at the second discharge in the range of 2.0–4.4 V vs. Li. This improvement of electrochemical performance compared to pristine V2O5 is attributed to the higher electric conductivity and enhanced bidimensionality. [Copyright &y& Elsevier]