skip to main content


Title: Eulerian Walks in Temporal Graphs
Abstract

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,λ), with$$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$λ:E(G)2[τ], an edge$$\varvec{e}\varvec{\in } \varvec{E(G)}$$eE(G)is available only at the times specified by$$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$λ(e)[τ], 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,λ)has a temporal walk or trail is polynomial, while deciding whether it has a local trail is$$\varvec{\texttt {NP}}$$NP-complete even if$$\varvec{\tau = 2}$$τ=2. In contrast, in the general case, solving any of these problems is$$\varvec{\texttt {NP}}$$NP-complete, even under very strict hypotheses. We finally give$$\varvec{\texttt {XP}}$$XPalgorithms parametrized by$$\varvec{\tau }$$τfor walks, and by$$\varvec{\tau +tw(G)}$$τ+tw(G)for trails and local trails, where$$\varvec{tw(G)}$$tw(G)refers to the treewidth of$$\varvec{G}$$G.

 
more » « less
NSF-PAR ID:
10370097
Author(s) / Creator(s):
;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Algorithmica
Volume:
85
Issue:
3
ISSN:
0178-4617
Page Range / eLocation ID:
p. 805-830
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    The radiation of steady surface gravity waves by a uniform stream$$U_{0}$$U0over locally confined (width$$L$$L) smooth topography is analyzed based on potential flow theory. The linear solution to this classical problem is readily found by Fourier transforms, and the nonlinear response has been studied extensively by numerical methods. Here, an asymptotic analysis is made for subcritical flow$$D/\lambda > 1$$D/λ>1in the low-Froude-number ($$F^{2} \equiv \lambda /L \ll 1$$F2λ/L1) limit, where$$\lambda = U_{0}^{2} /g$$λ=U02/gis the lengthscale of radiating gravity waves and$$D$$Dis the uniform water depth. In this regime, the downstream wave amplitude, although formally exponentially small with respect to$$F$$F, is determined by a fully nonlinear mechanism even for small topography amplitude. It is argued that this mechanism controls the wave response for a broad range of flow conditions, in contrast to linear theory which has very limited validity.

     
    more » « less
  2. Abstract

    Extensional flow properties of polymer solutions in volatile solvents govern many industrially-relevant coating processes, but existing instrumentation lacks the environment necessary to control evaporation. To mitigate evaporation during dripping-onto-substrate (DoS) extensional rheology measurements, we developed a chamber to enclose the sample in an environment saturated with solvent vapor. We validated the evaporation-controlled DoS device by measuring a model high molecular weight polyethylene oxide (PEO) in various organic solvents both inside and outside of the chamber. Evaporation substantially increased the extensional relaxation time$$\lambda _{E}$$λEfor PEO in volatile solvents like dichloromethane and chloroform. PEO/chloroform solutions displayed an over 20-fold increase in$$\lambda _{E}$$λEdue to the formation of an evaporation-induced surface film; evaporation studies confirmed surface features and skin formation reminiscent of buckling instabilities commonly observed in drying polymer solutions. Finally, the relaxation times of semi-dilute PEO/chloroform solutions were measured with environmental control, where$$\lambda _{E}$$λEscaled with concentration by the exponent$$m=0.62$$m=0.62. These measurements validate the evaporation-controlled DoS environment, and confirm that chloroform is a good solvent for PEO, with a Flory exponent of$$\nu =0.54$$ν=0.54. Our results are the first to control evaporation during DoS extensional rheology, and provide guidelines establishing when environmental control is necessary to obtain accurate rheological parameters.

     
    more » « less
  3. Abstract

    We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$0-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$0-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$Ax=b, where$$A\in \mathbb {Z}^{m\times n}$$AZm×n,$${\varvec{b}}\in \mathbb {Z}^m$$bZmand$$\varvec{x}$$xis either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$0-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$R, to other subdomains such as$$\mathbb {Z}$$Z. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.

     
    more » « less
  4. Abstract

    We present a proof of concept for a spectrally selective thermal mid-IR source based on nanopatterned graphene (NPG) with a typical mobility of CVD-grown graphene (up to 3000$$\hbox {cm}^2\,\hbox {V}^{-1}\,\hbox {s}^{-1}$$cm2V-1s-1), ensuring scalability to large areas. For that, we solve the electrostatic problem of a conducting hyperboloid with an elliptical wormhole in the presence of anin-planeelectric field. The localized surface plasmons (LSPs) on the NPG sheet, partially hybridized with graphene phonons and surface phonons of the neighboring materials, allow for the control and tuning of the thermal emission spectrum in the wavelength regime from$$\lambda =3$$λ=3to 12$$\upmu$$μm by adjusting the size of and distance between the circular holes in a hexagonal or square lattice structure. Most importantly, the LSPs along with an optical cavity increase the emittance of graphene from about 2.3% for pristine graphene to 80% for NPG, thereby outperforming state-of-the-art pristine graphene light sources operating in the near-infrared by at least a factor of 100. According to our COMSOL calculations, a maximum emission power per area of$$11\times 10^3$$11×103W/$$\hbox {m}^2$$m2at$$T=2000$$T=2000K for a bias voltage of$$V=23$$V=23V is achieved by controlling the temperature of the hot electrons through the Joule heating. By generalizing Planck’s theory to any grey body and deriving the completely general nonlocal fluctuation-dissipation theorem with nonlocal response of surface plasmons in the random phase approximation, we show that the coherence length of the graphene plasmons and the thermally emitted photons can be as large as 13$$\upmu$$μm and 150$$\upmu$$μm, respectively, providing the opportunity to create phased arrays made of nanoantennas represented by the holes in NPG. The spatial phase variation of the coherence allows for beamsteering of the thermal emission in the range between$$12^\circ$$12and$$80^\circ$$80by tuning the Fermi energy between$$E_F=1.0$$EF=1.0eV and$$E_F=0.25$$EF=0.25eV through the gate voltage. Our analysis of the nonlocal hydrodynamic response leads to the conjecture that the diffusion length and viscosity in graphene are frequency-dependent. Using finite-difference time domain calculations, coupled mode theory, and RPA, we develop the model of a mid-IR light source based on NPG, which will pave the way to graphene-based optical mid-IR communication, mid-IR color displays, mid-IR spectroscopy, and virus detection.

     
    more » « less
  5. Abstract

    The search for neutrino events in correlation with gravitational wave (GW) events for three observing runs (O1, O2 and O3) from 09/2015 to 03/2020 has been performed using the Borexino data-set of the same period. We have searched for signals of neutrino-electron scattering and inverse beta-decay (IBD) within a time window of$$\pm \, 1000$$±1000 s centered at the detection moment of a particular GW event. The search was done with three visible energy thresholds of 0.25, 0.8 and 3.0 MeV. Two types of incoming neutrino spectra were considered: the mono-energetic line and the supernova-like spectrum. GW candidates originated by merging binaries of black holes (BHBH), neutron stars (NSNS) and neutron star and black hole (NSBH) were analyzed separately. Additionally, the subset of most intensive BHBH mergers at closer distances and with larger radiative mass than the rest was considered. In total, follow-ups of 74 out of 93 gravitational waves reported in the GWTC-3 catalog were analyzed and no statistically significant excess over the background was observed. As a result, the strongest upper limits on GW-associated neutrino and antineutrino fluences for all flavors ($$\nu _e, \nu _\mu , \nu _\tau $$νe,νμ,ντ) at the level$$10^9{-}10^{15}~\textrm{cm}^{-2}\,\textrm{GW}^{-1}$$109-1015cm-2GW-1have been obtained in the 0.5–5 MeV neutrino energy range.

     
    more » « less