Search

Two of the most widely used approaches to obtain polynomial-time approximation schemes (PTASs) on planar graphs are the Lipton-Tarjan separator-based approach and Baker's approach. In 2005, Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained efficient polynomial-time approximation schemes (EPTASs) for several problems, including Connected Dominating Set and Feedback Vertex Set. In this work, we unify the two strengthened approaches to combine the best of both worlds. We develop a framework allowing the design of EPTAS on classes of graphs with the subquadratic grid minor (SQGM) property. Roughly speaking, a class of graphs has the SQGM property if, for every graph G from the class, the fact that G contains no t × t grid as a minor guarantees that the treewidth of G is subquadratic in t. For example, the class of planar graphs and, more generally, classes of graphs excluding some fixed graph as a minor, have the SQGM property. At the heart of our framework is a decomposition lemma stating that for "most" bidimensional problems on a graph class G with the SQGM property, there is a polynomial-time algorithm that, given a graph G ∈ G as input and an ϵ > 0, outputs a vertex set X of size ϵ · OPT such that the tree width of G - X is f (ϵ). Here, OPT is the objective function value of the problem in question and f is a function depending only on ϵ. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework aswell as for awide range of packing problems, partial covering problems and problems that are neither closed under taking minors nor contractions. To the best of our knowledge, for many of these problems--including Cycle Packing, F -Packing, F -Deletion, Max Leaf Spanning Tree, or Partial r-Dominating Set--no EPTASs, even on planar graphs, were previously known. We also prove novel excluded grid theorems in unit disk and map graphs without large cliques. Using these theorems, we show that these classes of graphs have the SQGM property. Based on the developed framework, we design EPTASs and subexponential time parameterized algorithms for various classes of problems on unit disk and map graphs. [ABSTRACT FROM AUTHOR]

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]

Let CMSO denote the counting monadic second-order logic of graphs. We give a constructive proof that for some computable function f, there is an algorithm A that takes as input a CMSO sentence ', a positive integer t, and a connected graph G of maximum degree at most -, and determines, in time f(j'j; t) x 20(t) x jGjO(t), whether G has a supergraph G0 of treewidth at most t such that G0 j= '. The algorithmic metatheorem described above sheds new light on certain unresolved questions within the framework of graph completion algorithms. In particular, using this metatheorem, we provide an explicit algorithm that determines, in time f(d)x2O(d)xjGjO(d), whether a connected graph of maximum degree x has a planar supergraph of diameter at most d. Additionally, we show that for each fixed k, the problem of determining whether G has an k-outerplanar supergraph of diameter at most d is strongly uniformly fixed parameter tractable with respect to the parameter d. This result can be generalized in two directions. First, the diameter parameter can be replaced by any contraction-closed effectively CMSO-definable parameter p. Examples of such parameters are vertex-cover number, dominating number, and many other contractionbidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth. [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]

Game developers, even during the early years of game design, have always searched for new and interesting ways of creating more elaborate, immersive and realistic environments for their video games.

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]

Abstract: We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [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: We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [Copyright &y& Elsevier]

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]