We create a framework for hereditary graph classes $\mathcal{G}^\delta$ built on a two-dimensional grid of vertices and edge sets defined by a triple $\delta=\{\alpha,\beta,\gamma\}$ of objects that define edges between consecutive columns, edges between non-consecutive columns (called bonds), and edges within columns. This framework captures all previously proven minimal hereditary classes of graph of unbounded clique-width, and many new ones, although we do not claim this includes all such classes. We show that a graph class $\mathcal{G}^\delta$ has unbounded clique-width if and only if a certain parameter $\mathcal{N}^\delta$ is unbounded. We further show that $\mathcal{G}^\delta$ is minimal of unbounded clique-width (and, indeed, minimal of unbounded linear clique-width) if another parameter $\mathcal{M}^\beta$ is bounded, and also $\delta$ has defined recurrence characteristics. Both the parameters $\mathcal{N}^\delta$ and $\mathcal{M}^\beta$ are properties of a triple $\delta=(\alpha,\beta,\gamma)$, and measure the number of distinct neighbourhoods in certain auxiliary graphs. Throughout our work, we introduce new methods to the study of clique-width, including the use of Ramsey theory in arguments related to unboundedness, and explicit (linear) clique-width expressions for subclasses of minimal classes of unbounded clique-width.
相關內容
For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a dominating broadcast on $ G $. The cost of the dominating broadcast $f$ is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the broadcast domination number of $G$, denoted by $ \gamma_{b}(G) $. A multipacking is a set $ S \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ S $, that is, there are at most $ r $ vertices in $ S $ at a distance at most $ r $ from $ v $ in $ G $. The multipacking number of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. We show that, for any connected chordal graph $G$, $\gamma_{b}(G)\leq \big\lceil{\frac{3}{2} mp(G)\big\rceil}$. We also show that $\gamma_b(G)-mp(G)$ can be arbitrarily large for connected chordal graphs by constructing an infinite family of connected chordal graphs such that the ratio $\gamma_b(G)/mp(G)=10/9$, with $mp(G)$ arbitrarily large. Moreover, we show that $\gamma_{b}(G)\leq \big\lfloor{\frac{3}{2} mp(G)+2\delta\big\rfloor} $ holds for all $\delta$-hyperbolic graphs. In addition, we provide a polynomial-time algorithm to construct a multipacking of a $\delta$-hyperbolic graph $G$ of size at least $ \big\lceil{\frac{2mp(G)-4\delta}{3} \big\rceil} $.
A multifold $1$-perfect code ($1$-perfect code for list decoding) in any graph is a set $C$ of vertices such that every vertex of the graph is at distance not more than $1$ from exactly $\mu$ elements of $C$. In $q$-ary Hamming graphs, where $q$ is a prime power, we characterize all parameters of multifold $1$-perfect codes and all parameters of additive multifold $1$-perfect codes. In particular, we show that additive multifold $1$-perfect codes are related to special multiset generalizations of spreads, multispreads, and that multispreads of parameters corresponding to multifold $1$-perfect codes always exist. Keywords: perfect codes, multifold packing, multiple covering, list-decoding codes, additive codes, spreads, multispreads, completely regular codes, intriguing sets.
The objective of this article is to address the discretisation of fractured/faulted poromechanical models using 3D polyhedral meshes in order to cope with the geometrical complexity of faulted geological models. A polytopal scheme is proposed for contact-mechanics, based on a mixed formulation combining a fully discrete space and suitable reconstruction operators for the displacement field with a face-wise constant approximation of the Lagrange multiplier accounting for the surface tractions along the fracture/fault network. To ensure the inf--sup stability of the mixed formulation, a bubble-like degree of freedom is included in the discrete space of displacements (and taken into account in the reconstruction operators). It is proved that this fully discrete scheme for the displacement is equivalent to a low-order Virtual Element scheme, with a bubble enrichment of the VEM space. This $\mathbb{P}^1$-bubble VEM--$\mathbb{P}^0$ mixed discretization is combined with an Hybrid Finite Volume scheme for the Darcy flow. All together, the proposed approach is adapted to complex geometry accounting for network of planar faults/fractures including corners, tips and intersections; it leads to efficient semi-smooth Newton solvers for the contact-mechanics and preserve the dissipative properties of the fully coupled model. Our approach is investigated in terms of convergence and robustness on several 2D and 3D test cases using either analytical or numerical reference solutions both for the stand alone static contact mechanical model and the fully coupled poromechanical model.
A class of (block) rational Krylov subspace based projection method for solving large-scale continuous-time algebraic Riccati equation (CARE) $0 = \mathcal{R}(X) := A^HX + XA + C^HC - XBB^HX$ with a large, sparse $A$ and $B$ and $C$ of full low rank is proposed. The CARE is projected onto a block rational Krylov subspace $\mathcal{K}_j$ spanned by blocks of the form $(A^H+ s_kI)C^H$ for some shifts $s_k, k = 1, \ldots, j.$ The considered projections do not need to be orthogonal and are built from the matrices appearing in the block rational Arnoldi decomposition associated to $\mathcal{K}_j.$ The resulting projected Riccati equation is solved for the small square Hermitian $Y_j.$ Then the Hermitian low-rank approximation $X_j = Z_jY_jZ_j^H$ to $X$ is set up where the columns of $Z_j$ span $\mathcal{K}_j.$ The residual norm $\|R(X_j )\|_F$ can be computed efficiently via the norm of a readily available $2p \times 2p$ matrix. We suggest to reduce the rank of the approximate solution $X_j$ even further by truncating small eigenvalues from $X_j.$ This truncated approximate solution can be interpreted as the solution of the Riccati residual projected to a subspace of $\mathcal{K}_j.$ This gives us a way to efficiently evaluate the norm of the resulting residual. Numerical examples are presented.
Text prompts are crucial for generalizing pre-trained open-set object detection models to new categories. However, current methods for text prompts are limited as they require manual feedback when generalizing to new categories, which restricts their ability to model complex scenes, often leading to incorrect detection results. To address this limitation, we propose a novel visual prompt method that learns new category knowledge from a few labeled images, which generalizes the pre-trained detection model to the new category. To allow visual prompts to represent new categories adequately, we propose a statistical-based prompt construction module that is not limited by predefined vocabulary lengths, thus allowing more vectors to be used when representing categories. We further utilize the category dictionaries in the pre-training dataset to design task-specific similarity dictionaries, which make visual prompts more discriminative. We evaluate the method on the ODinW dataset and show that it outperforms existing prompt learning methods and performs more consistently in combinatorial inference.
By approximating posterior distributions with weighted samples, particle filters (PFs) provide an efficient mechanism for solving non-linear sequential state estimation problems. While the effectiveness of particle filters has been recognised in various applications, their performance relies on the knowledge of dynamic models and measurement models, as well as the construction of effective proposal distributions. An emerging trend involves constructing components of particle filters using neural networks and optimising them by gradient descent, and such data-adaptive particle filtering approaches are often called differentiable particle filters. Due to the expressiveness of neural networks, differentiable particle filters are a promising computational tool for performing inference on sequential data in complex, high-dimensional tasks, such as vision-based robot localisation. In this paper, we review recent advances in differentiable particle filters and their applications. We place special emphasis on different design choices for key components of differentiable particle filters, including dynamic models, measurement models, proposal distributions, optimisation objectives, and differentiable resampling techniques.
The generalized additive Runge-Kutta (GARK) framework provides a powerful approach for solving additively partitioned ordinary differential equations. This work combines the ideas of symplectic GARK schemes and multirate GARK schemes to efficiently solve additively partitioned Hamiltonian systems with multiple time scales. Order conditions, as well as conditions for symplecticity and time-reversibility, are derived in the general setting of non-separable Hamiltonian systems. Investigations of the special case of separable Hamiltonian systems are also carried out. We show that particular partitions may introduce stability issues, and discuss partitions that enable an implicit-explicit integration leading to improved stability properties. Higher-order symplectic multirate GARK schemes based on advanced composition techniques are discussed. The performance of the schemes is demonstrated by means of the Fermi-Pasta-Ulam problem.
The problem of packing as many subgraphs isomorphic to $H \in \mathcal H$ as possible in a graph for a class $\mathcal H$ of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for $H$ that contains at least three vertices and at least three edges, respectively. In this paper, we consider ``list variants'' of these problems: Given a graph $G$, an integer $k$, and a collection $\mathcal L_{\mathcal H}$ of subgraphs of $G$ isomorphic to some $H \in \mathcal H$, the goal is to compute $k$ subgraphs in $\mathcal L_{\mathcal H}$ that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.
We present a novel deep learning method for estimating time-dependent parameters in Markov processes through discrete sampling. Departing from conventional machine learning, our approach reframes parameter approximation as an optimization problem using the maximum likelihood approach. Experimental validation focuses on parameter estimation in multivariate regression and stochastic differential equations (SDEs). Theoretical results show that the real solution is close to SDE with parameters approximated using our neural network-derived under specific conditions. Our work contributes to SDE-based model parameter estimation, offering a versatile tool for diverse fields.
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extend of our knowledge, the first approach that deals with pair potentials of unbounded range. We compare the resulting algorithms with recently established results and study further properties of the random geometric graphs with respect to the hard-core model.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191