We present a linear-time algorithm for deciding first-order logic (FOL) properties in classes of graphs with bounded expansion. Many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all ...
详细信息
We present a linear-time algorithm for deciding first-order logic (FOL) properties in classes of graphs with bounded expansion. Many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no sub graph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We also develop an almost linear-time algorithm for deciding FOL properties in classes of graphs with locally bounded expansion, those include classes of graphs with locally bounded tree-width or locally excluding a minor. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FOL property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their addition results in a graph in the class. In addition, we design a dynamic data structure for testing existential properties or the existence of short paths between prescribed vertices in such classes of graphs. All our results also hold for relational structures and are based on the seminal result of Nesetril and Ossona de Mendez on the existence of low tree-depth colorings.
The indium-rich InSb(001) surface, that shows the c(8×2) reconstruction at room temperature and a partially disordered phase at 77 K (the low temperature or LT phase), is studied experimentally by means of scanni...
The indium-rich InSb(001) surface, that shows the c(8×2) reconstruction at room temperature and a partially disordered phase at 77 K (the low temperature or LT phase), is studied experimentally by means of scanning probe microscopies, low-energy electron diffraction, and angle-resolved photoelectron spectroscopy (ARPES), as well as theoretically, using the density-functional theory (DFT). The experimental studies are done both at room temperature and at cryogenic temperatures. No metallic surface bands are found using ARPES, consequently the idea of charge-density waves as a possible explanation of the LT phase suggested previously by Goryl et al. [Surf. Sci. 601, 3605 (2007)] is discarded. On the other hand it is shown that an essential core of the surface structure is described by the so-called ζ model which has the c(8×2) symmetry. However, on top of this basic structure there are additional not fully occupied indium-atom rows. Vacancies/atoms in these rows rapidly fluctuate at room temperature while, upon cooling down, they stabilize to form a sublattice also of c(8×2) symmetry. Furthermore, this sublattice has shifted mirror symmetry axes (relating to those of the underlying ζ lattice) therefore the surface symmetry is lowered from c2mm to p2 and structural domains are formed. This occurs with no significant core ζ lattice distortions but dense domain borders lead to significant disorder in the top atomic layer. DFT calculations confirm that the postulated ζ-like structure with additional 50% occupied indium-atom rows is stable on the InSb (001) surface. Calculated, in the Tersoff-Hammann approximation, scanning tunneling microscopy (STM) images of the relaxed surface structure agree well with experimental STM images.
We construct new numerical solutions describing charged anti‐de Sitter black holes coupled to nonlinear Born‐Infeld electrodynamics within a certain class of scalar‐tensor theories and we study their thermodynamic ...
We construct new numerical solutions describing charged anti‐de Sitter black holes coupled to nonlinear Born‐Infeld electrodynamics within a certain class of scalar‐tensor theories and we study their thermodynamic phase structure. It is shown that for certain charge intervals phase transitions of zeroth and first order exist.
In this work are reported some new azo- functionalized azulene derivatives of nonlinear optical properties (NLO). They were studied using standard methods like degenerate four wave mixing, second - and third harmonic ...
详细信息
ISBN:
(纸本)9781424477999
In this work are reported some new azo- functionalized azulene derivatives of nonlinear optical properties (NLO). They were studied using standard methods like degenerate four wave mixing, second - and third harmonic generation and nonlinear optical absorption. The obtained results let to conclude that NLO properties of azulene molecule can be significantly enhanced by substitution with electron accepting thiazole group.
The increase of radiation intensity measured by a proportional counter leads to the undesirable changes of its parameters, such as pulse height and energy resolution. It has been found that both the pulse height and t...
Relevance of the Mössbauer spectroscopy in the investigation of the σ-phase in Fe-Cr and Fe-V systems, base alloys for technologically important steels, will be demonstrated by showing its standard applications ...
详细信息
Structure refinement of the basic Ni-rich Al-Ni-Co decagonal phase was performed in physical space. Statistical approach was used to derive the structure factor. Rhombic Penrose tiling with an edge length of 10.28 ...
Structure refinement of the basic Ni-rich Al-Ni-Co decagonal phase was performed in physical space. Statistical approach was used to derive the structure factor. Rhombic Penrose tiling with an edge length of 10.28 Å was chosen as a reference lattice. The best-fit structure model with 106 parameters and 2767 reflections gives R = 12.3% and wR = 6.2%. The observations-to-parameters ratio is high – 26.1 Density and chemical composition of the resulting structure are very close to experimental values.
Stability of (Mg-Al) clusters in the β-Mg2Al3 structure has been studied with the use of the effective pair potential of interatomic interactions taken from ab-initio calculations. The total potential energy has been...
Stability of (Mg-Al) clusters in the β-Mg2Al3 structure has been studied with the use of the effective pair potential of interatomic interactions taken from ab-initio calculations. The total potential energy has been calculated for various possible (Mg-Al) cluster configurations in order to find the optimal ones. The computation has been started from the cluster located at the 8(b) site consisting of 72 partially occupied, overlapping atomic sites, as determined by X-ray studies. The configurations of fully occupied, non-overlaping atomic positions have been selected using the criterion of minimal potential energy. The simulated annealing algorithm has been used for further optimization of the atomic positions in 3D space. The energy optimization leads to the selection of several configurations with the energy close to the minimum. For such structures the configuration entropy has been calculated as a function of the total potential energy. More complex structures, consisting of the optimized clusters and various interface configurations, have been also studied.
A large enhancement of the x-ray magnetic circular dichroism is observed at the iron K absorption preedge of magnetite. This is achieved by performing resonant inelastic x-ray scattering (RIXS) experiments with a 2p h...
详细信息
A large enhancement of the x-ray magnetic circular dichroism is observed at the iron K absorption preedge of magnetite. This is achieved by performing resonant inelastic x-ray scattering (RIXS) experiments with a 2p hole in the final state of the second-order optical process. We measured and calculated the full 1s2p RIXS planes for opposite helicities of the incoming circularly polarized x rays. The crystal field multiplet calculations show that the enhancement arises from 2p−3d Coulomb repulsions and 2p and 3d spin-orbit coupling. The observed magnitude of the RIXS magnetic circular dichroism effect is ∼16%. This opens up new opportunities for a broad range of research fields allowing for truly bulk-sensitive, element-, and site-selective measurements of 3d transition metal magnetic moments and their ordering using hard x-ray photons.
The symmetry of magnesium borohydride Mg(BH4)2 has been analyzed. In particular, relations between space groups I41/amd(IT 141), I-4m2(IT 119) and F222(IT 22) have been derived. As a result of the analysis based on th...
The symmetry of magnesium borohydride Mg(BH4)2 has been analyzed. In particular, relations between space groups I41/amd(IT 141), I-4m2(IT 119) and F222(IT 22) have been derived. As a result of the analysis based on the theory of the space groups and their representations we found all transformations from the parent structure, described by the high symmetry group, to the structures with symmetries belonging to the appropriate subgroups. For a given transformation we obtained the displacements of the atoms from their initial positions, the ordering of the hydrogen atoms over the interstitial sites and the ordering of the magnetic moments. In the description the number of free parameters has been reduced to the necessary minimum.
暂无评论