1971. Maximum matchings in geometric intersection graphsÉdouard Bonnet, Sergio Cabello, Wolfgang Mulzer, 2023, original scientific article Abstract: Let $G$ be an intersection graph of $n$ geometric objects in the plane. We show that a maximum matching in $G$ can be found in $O(\rho^{3\omega/2}n^{\omega/2})$ time with high probability, where $\rho$ is the density of the geometric objects and $\omega>2$ is a constant such that $n \times n$ matrices can be multiplied in $O(n^\omega)$ time. The same result holds for any subgraph of $G$, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in $O(n^{\omega/2})$ time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in $[1, \Psi]$ can be found in $O(\Psi^6\log^{11} n + \Psi^{12 \omega} n^{\omega/2})$ time with high probability.
Keywords: computational geometry, geometric intersection graphs, disk graphs, unit-disk graphs, matchings
Published in DiRROS: 08.04.2024; Views: 442; Downloads: 208
 Full text (576,69 KB)
This document has many files! More... |
1972. Maker-Breaker domination game on trees when Staller winsCsilla Bujtás, Pakanun Dokyeesun, Sandi Klavžar, 2023, original scientific article Abstract: In the Maker-Breaker domination game played on a graph $G$, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$ is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$ times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is obtained when there are at least two odd $n_i$s. If ▫$n_1$▫ and $n_2$ are the two smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$▫. For caterpillars, exact formulas for $\gamma_{\rm SMB}$ and for $\gamma_{\rm SMB}'$ are established.
Keywords: domination game, Maker-Breaker game, Maker-Breaker domination game, hypergraphs, trees, subdivided stars, caterpillars
Published in DiRROS: 08.04.2024; Views: 591; Downloads: 238
Full text (255,58 KB)
This document has many files! More... |
1973. The Calabi-Yau problem for minimal surfaces with Cantor endsFranc Forstnerič, 2023, original scientific article Abstract: We show that every connected compact or bordered Riemann surface contains a Cantor set whose complement admits a complete conformal minimal immersion in ${\mathbb R}^3$ with bounded image. The analogous result holds for holomorphic immersions into any complex manifold of dimension at least $2$, for holomorphic null immersions into ${\mathbb C}^n$ with $n \ge 3$, for holomorphic Legendrian immersions into an arbitrary complex contact manifold, and for superminimal immersions into any selfdual or anti-self-dual Einstein four-manifold.
Keywords: minimal surfaces, Calabi–Yau problem, null curve, Legendrian curve
Published in DiRROS: 08.04.2024; Views: 415; Downloads: 179
Full text (516,47 KB)
This document has many files! More... |
1974. Generalized Pell graphsVesna Iršič, Sandi Klavžar, Elif Tan, 2023, original scientific article Abstract: In this paper, generalized Pell graphs $\Pi_{n,k}$, $k\ge 2$, are introduced. The special case of $k=2$ are the Pell graphs $\Pi_{n}$ defined earlier by Munarini. Several metric, enumerative, and structural properties of these graphs are established. The generating function of the number of edges of $\Pi_{n,k}$ and the generating function of its cube polynomial are determined. The center of $\Pi_{n,k}$ is explicitly described; if $k$ is even, then it induces the Fibonacci cube $\Gamma_{n}$. It is also shown that $\Pi_{n,k}$ is a median graph, and that $\Pi_{n,k}$ embeds into a Fibonacci cube.
Keywords: Fibonacci cubes, Pell graphs, generating functions, center of graph, median graphs, k-Fibonacci sequence
Published in DiRROS: 08.04.2024; Views: 471; Downloads: 198
Full text (345,71 KB)
This document has many files! More... |
1975. |
1976. A coupled convective-diffusive model of heat transfer and melt-pool dynamics in additive manufacturingTijan Mede, Matjaž Godec, 2024, treatise, preliminary study, study Keywords: additive manufacturing, selective laser melting, laser powder-bed fusion, melt-pool, heat transfer, convection
Published in DiRROS: 05.04.2024; Views: 542; Downloads: 0 |
1977. Behaviour of the backfilled right bank of the Mavčiče damPavel Žvanut, Rude Brinšek, 2018, published scientific conference contribution Abstract: The Mavčiče concrete gravity dam, part of the corresponding hydro-power plant, was built on the Sava River, in Slovenia, in 1986. It has a maximum structural height of 38.5 m, and the dam crest has a length of 149 m. The dam structure consists of an erection bay, a machine hall, and two spillways, followed by an embankment dam. Most of the dam is founded on permeable Quaternary conglomerate bedrock, so that a cut-off grout curtain had to be constructed to a depth of up to 60 m below the ground surface, where a layer of impermeable Oligocene marine clay occurs. However, the erection bay, which is located on the right bank of the dam, is founded on a layer of gravel backfill, up to about 25 m thick, which lies on top of the conglomerate bedrock. Long-term manual technical monitoring of the behaviour of the dam began in 1986, and an automated monitoring system was established between 2003 and 2005. In general, the results of measurements and visual inspections did not show any abnormalities. However, this was not the case for the erection bay located on the top of the backfilled right bank of the dam, where the results of measurements of vertical displacements showed increasing settlements. By 1999, i.e. over a period of 12 years, these settlements had increased to 22 mm. The results of investigations, by drilling three research boreholes in 1993, and another six such boreholes in 1996, indicated that the settlements were the consequence of the secondary consolidation of the backfill, and probable also due to scouring of fine material from the backfill. Due to the resulting differential settlements, the crane rail which connects the erection bay to the machine hall, as well as the crane rail which is located along the crest of the dam, became nonfunctional, and needed height corrections. For this reason rehabilitation works of the backfill and of the substratum of the right bank of the dam were performed between September 1999 and August 2000, using 50 m long grouted boreholes. This grouting was performed using a combination of water reactive polyurethane and a cement-bentonite mixture. Measurements performed since than have shown that the settlement rate has slowed down slightly (by 2017, i.e. over the last 17 years, the settlements had increased by up to 8 mm), but from the point of view of the operation of the two crane rails the settlement process needed to be stopped. Additional investigations, involving the drilling of two research boreholes, as well as appropriate laboratory and field measurements, were performed between November 2015 and March 2016. According to the results of these most recent investigations, the newer settlements were the consequence of additional scouring of fine material from the backfill. In order to achieve a final solution to the problem of the subsidence of the erection bay, additional rehabilitation works of the backfill and substratum of the right bank of the dam, by grouting the permeable zones, would be needed in order to stop both the scouring of fine material from the backfill, as well as any internal erosion of the cavernous conglomerate at the base of the backfill. The latter concerns the long-term stability of the right bank of the dam with potentially serious results.
Keywords: concrete dams, gravity dams, Mavčiče Dam, Sava River, technical monitoring, geotechnical investigation, rehabilitation
Published in DiRROS: 05.04.2024; Views: 546; Downloads: 238
Full text (1,34 MB)
This document has many files! More... |
1978. Life cycle assessment of metal alloys for structural applicationsKatja Malovrh Rebec, Boštjan Markoli, Blaž Leskovar, 2018, published scientific conference contribution (invited lecture) Abstract: The study compared environmental footprints of two types of Al-alloys: well-known 5083 aluminium alloy with magnesium and traces of manganese and chromium in its composition. This material is highly resistant to seawater corrosion and the influence of industrial chemicals. Furthermore, it retains exceptional strength after welding. The comparisons were made to an innovative alloy where the aluminium based matrix is reinforced by metastable quasicrystals (QC), thus avoiding magnesium in its composition. Furthermore, we checked other aluminium ingots' footprints and compared European average and Germany country specific production data. Environmental footprints were assessed via cradle to gate life cycle assessment. Our findings normalized to 1 m2 plate suggest, that newly proposed alloy could save around 50 % in value of parameters abiotic resources depletion of fossil fuels, acidification, eutrophication, global warming potential and photochemical ozone creation potential if we compare Qc5 to 6 mm 5083 alloy plate. Only abiotic resources depletion of elements and ozone depletion parameters increase for Qc5 compared to 6 mm 5083 alloy plate.
Keywords: environmental footprints, LCA, Al-alloys
Published in DiRROS: 05.04.2024; Views: 450; Downloads: 210
Full text (2,29 MB)
This document has many files! More... |
1979. Improving uncertainty of strain gauge bridge standardsMiha Hiti, 2018, published scientific conference contribution Abstract: The article proposes a procedure for calibration of strain gauge bridge standards with improved relative calibration uncertainty. In contrast to a typical calibration with voltage ratio standards or comparison calibration with other bridge standards, the proposed procedure uses a calibrated reference bridge amplifier, additionally evaluated using combinatorial calibration technique to improve its calibration uncertainty. The resulting uncertainty of ratio steps referenced to zero ratio step is lower than the traditional uncertainty achieved through direct independent traceability to mVV−1 ratio values. The proposed procedure enables direct application of the calibrated bridge standard values with low relative uncertainty for calibration of bridge amplifiers, without the need for additional combinatorial evaluation of each individual bridge amplifier.
Keywords: voltage ratio, linearity check, bridge standard, calibration
Published in DiRROS: 05.04.2024; Views: 350; Downloads: 215
Full text (775,45 KB)
This document has many files! More... |
1980. |
