More Like this

1. Eulerian Walks in Temporal Graphs

   https://doi.org/10.1007/s00453-022-01021-y  

   Marino, Andrea ; Silva, Ana ( August 2022 , Algorithmica)

   An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graphGat least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph$$\varvec{(G,\lambda )}$$$(G,\lambda )$, with$$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$$\lambda :E\left(G\right)\to 2^{\left[\tau \right]}$, an edge$$\varvec{e}\varvec{\in } \varvec{E(G)}$$$e\in E\left(G\right)$is available only at the times specified by$$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$$\lambda \left(e\right)\subseteq \left[\tau \right]$, in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether$$\varvec{(G,\lambda )}$$$(G,\lambda )$has a temporal walk or trail is polynomial, while deciding whether it has a local trail is$$\varvec{\texttt {NP}}$$$\mathrm{NP}$-complete even if$$\varvec{\tau = 2}$$$\tau =2$. In contrast, in the general case, solving any of these problems is$$\varvec{\texttt {NP}}$$$\mathrm{NP}$-complete, even under very strict hypotheses. We finally give$$\varvec{\texttt {XP}}$$$\mathrm{XP}$algorithms parametrized by$$\varvec{\tau }$$$\tau$for walks, and by$$\varvec{\tau +tw(G)}$$$\tau +tw\left(G\right)$for trails and local trails, where$$\varvec{tw(G)}$$$tw\left(G\right)$refers to the treewidth of$$\varvec{G}$$$G$.

    

   more » « less
2. Polymer multilayer films for high temperature capacitor application

   https://doi.org/10.1002/app.47535  

   Yin, Kezhen ; Zhang, Jingwei ; Li, Zhenpeng ; Feng, Jingxing ; Zhang, Ci ; Chen, Xinyue ; Olah, Andrew ; Schuele, Donald E. ; Zhu, Lei ; Baer, Eric ( January 2019 , Journal of Applied Polymer Science)

   Advanced film capacitors require polymers with high thermal stability, high breakdown strength, and low loss for high temperature dielectric applications. To fulfill such requirements, two polymer multilayer film systems were coextruded via the forced assembly technique. High glass transition temperature (T_g) polycarbonate (HTPC,T_g = 165 °C) and polysulfone (PSF,T_g = 185 °C) were multilayered with a high dielectric constant polymer, poly(vinylidene fluoride) (PVDF), respectively. The PSF/PVDF system was more thermally stable than the HTPC/PVDF system because of the higherT_gfor PSF. At temperatures lower than 170 °C, the HTPC/PVDF system exhibited comparable breakdown strength and hysteresis loss as the PSF/PVDF system. While at temperatures above 170 °C, the PSF/PVDF system exhibited a higher breakdown strength because of the higherT_gof PSF. The electric displacement‐electric field (D‐E) loop behavior of the PSF/PVDF system was studied as a function of temperature. Moreover, a melt‐recrystallization process could further decrease the hysteresis loss for the PSF/PVDF system due to better edge‐on crystal orientation. These results demonstrate that PSF/PVDF and HTPC/PVDF systems are applicable for high temperature film capacitors. © 2019 Wiley Periodicals, Inc. J. Appl. Polym. Sci.2019,136, 47535.

    

   more » « less
3. Disproof of a packing conjecture of Alon and Spencer

   https://doi.org/10.1002/rsa.20884  

   Acan, Hüseyin ; Kahn, Jeff ( July 2019 , Random Structures & Algorithms)

   A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graphG_n,1/2typically admits a covering of a constant fraction of its edges by edge‐disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: forandA₁,…,A_tchosen uniformly and independently from thek‐subsets of {1,…,n}, what can one say aboutOur main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently.

    

   more » « less
4. Measuring the Temperature of Starspots from Multi-filter Photometry

   https://doi.org/10.3847/1538-3881/ace59c  

   Schutte, Maria C. ; Hebb, Leslie ; Wisniewski, John P. ; Cañas, Caleb I. ; Libby-Roberts, Jessica E. ; Lin, Andrea S. J. ; Robertson, Paul ; Stefánsson, Gumundur ( August 2023 , The Astronomical Journal)

   Using simultaneous multi-filter observations during the transit of an exoplanet around a K dwarf star, we determine the temperature of a starspot through modeling the radius and position with wavelength-dependent spot contrasts. We model the spot using the starspot modeling program STarSPot (STSP), which uses the transiting companion as a knife-edge probe of the stellar surface. The contrast of the spot, i.e., the ratio of the integrated flux of a darker spot region to the star's photosphere, is calculated for a range of filters and spot temperatures. We demonstrate this technique using simulated data of HAT-P-11, a K dwarf (T_eff= 4780 K) with well-modeled starspot properties for which we obtained simultaneous multi-filter transits using Las Cumbres Observatory's MuSCAT3 instrument on the 2m telescope at Haleakala Observatory, which allows for simultaneous, multi-filter, diffuser-assisted high-precision photometry. We determine the average (i.e., a combination of penumbra and umbra) spot temperature for HAT-P-11's spot complexes is 4500 K ± 100 K using this technique. We also find for our set of filters that comparing the SDSS$g^{\prime }$and$i^{\prime }$filters maximizes the signal difference caused by a large spot in the transit. Thus, this technique allows for the determination of the average spot temperature using only one spot occultation in transit and can provide simultaneous information on the spot temperature and spot properties.

    

   more » « less
5. Computing β-Stretch Paths in Drawings of Graphs

   Arkin, E ; Darabi, F ; Efrat, A ; Frank, F ; Fulek, R ; Kobourov, S ; Mitchell, J ( October 2020 , 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT))

   Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the sub-curve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log |V (G)|)), and s, t ∈ V (G), outputs a β-stretch path between s and t, if a (1 − ε)β-stretch path between s and t exists in the drawing. 

   more » « less