Explore the vast range of titles available.

SciPy is an open-source scientific computing library for the Python programming language. Since its initial release in 2001, SciPy has become a de facto standard for leveraging scientific algorithms in Python, with over 600 unique code contributors, thousands of dependent packages, over 100,000 dependent repositories and millions of downloads per year. In this work, we provide an overview of the capabilities and development practices of SciPy 1.0 and highlight some recent technical developments. This Perspective describes the development and capabilities of SciPy 1.0, an open source scientific computing library for the Python programming language.

A distributed graph algorithm is basically an algorithm where every node of a graph can look at its neighborhood at some distance in the graph and chose its output. As distributed environment are subject to faults, an important issue is to be able to check that the output is correct, or in general that the network is in proper configuration with respect to some predicate. One would like this checking to be very local, to avoid using too much resources. Unfortunately most predicates cannot be checked this way, and that is where certification comes into play. Local certification (also known as proof-labeling schemes, locally checkable proofs or distributed verification) consists in assigning labels to the nodes, that certify that the configuration is correct. There are several point of view on this topic: it can be seen as a part of self-stabilizing algorithms, as labeling problem, or as a non-deterministic distributed decision. This paper is an introduction to the domain of local certification, giving an overview of the history, the techniques and the current research directions.

We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph$G = (V,E)$and an integer$k \\in \\mathbb{N}$and seeks to edit (add or delete) at most$k$edges from$G$to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide$O(k^2)$vertex-kernels for Block Graph Editing and Block Graph Deletion,$O(k^3)$vertex-kernels for Strictly Chordal Completion and Strictly Chordal Deletion and a$O(k^4)$vertex-kernel for Strictly Chordal Editing.

Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as \"interval thinness\" and \"fellow traveler property\". Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., COMPLEX NETWORKS'21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.

In Defective Coloring we are given a graph$G$and two integers$\\chi_d$ ,$\\Delta^*$and are asked if we can$\\chi_d$ -color$G$so that the maximum degree induced by any color class is at most$\\Delta^*$ . We show that this natural generalization of Coloring is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters$\\chi_d$ ,$\\Delta^*$is set to the smallest possible fixed value that does not trivialize the problem ( $\\chi_d = 2$or$\\Delta^* = 1$ ). Together with a simple treewidth-based DP algorithm this completely determines the complexity of the problem also on chordal graphs. We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that Defective Coloring is in P for cographs if either$\\chi_d$or$\\Delta^*$is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both$\\chi_d$and$\\Delta^*$are unbounded.

Given two integers$\\ell$and$p$as well as$\\ell$graph classes$\\mathcal{H}_1,\\ldots,\\mathcal{H}_\\ell$ , the problems$\\mathsf{GraphPart}(\\mathcal{H}_1, \\ldots, \\mathcal{H}_\\ell,p)$ ,$\\mathsf{VertPart}(\\mathcal{H}_1, \\ldots, \\mathcal{H}_\\ell)$ , and$\\mathsf{EdgePart}(\\mathcal{H}_1, \\ldots, \\mathcal{H}_\\ell)$ask, given graph$G$as input, whether$V(G)$ ,$V(G)$ ,$E(G)$respectively can be partitioned into$\\ell$sets$S_1, \\ldots, S_\\ell$such that, for each$i$between$1$and$\\ell$ ,$G[S_i] \\in \\mathcal{H}_i$ ,$G[S_i] \\in \\mathcal{H}_i$ ,$(V(G),S_i) \\in \\mathcal{H}_i$respectively. Moreover in$\\mathsf{GraphPart}(\\mathcal{H}_1, \\ldots, \\mathcal{H}_\\ell,p)$ , we request that the number of edges with endpoints in different sets of the partition is bounded by$p$ . We show that if there exist dynamic programming tree-decomposition-based algorithms for recognizing the graph classes$\\mathcal{H}_i$ , for each$i$ , then we can constructively create a dynamic programming tree-decomposition-based algorithms for$\\mathsf{GraphPart}(\\mathcal{H}_1, \\ldots, \\mathcal{H}_\\ell,p)$ ,$\\mathsf{VertPart}(\\mathcal{H}_1, \\ldots, \\mathcal{H}_\\ell)$ , and$\\mathsf{EdgePart}(\\mathcal{H}_1, \\ldots, \\mathcal{H}_\\ell)$ . We apply this approach to known problems. For well-studied problems, like VERTEX COVER and GRAPH$q$ -COLORING, we obtain running times that are comparable to those of the best known problem-specific algorithms. For an exotic problem from bioinformatics, called DISPLAYGRAPH, this approach improves the known algorithm parameterized by treewidth.

In the Fully Leafed Induced Subtrees, one is given a graph$G$and two integers$a$and$b$and the question is to find an induced subtree of$G$with$a$vertices and at least$b$leaves. This problem is known to be NP-complete even when the input graph is$4$ -regular. Polynomial algorithms are known when the input graph is restricted to be a tree or series-parallel. In this paper we generalize these results by providing an FPT algorithm parameterized by treewidth. We also provide a polynomial algorithm when the input graph is restricted to be a chordal graph. arXiv admin note: substantial text overlap with arXiv:1704.07284, arXiv:2103.06536

This paper presents two MATLAB codes for topology optimization of multi-material piezoelectric actuators and energy harvesters. These codes provide the extensions of the previously published 2D topology optimization codes for piezoelectric actuators and energy harvesters (Struct Multidisc Optim 63 (2), 983- 1014) with two major contributions: 1) extension to the third dimension, 2) combination of piezoelectric (active) and non-piezoelectric(passive) materials in the design domain. The codes are written in the most flexible form to be compatible with different optimization problems and practical case studies of piezoelectricity that exist in the literature. The codes address unique challenges that emerge by introducing the third dimension to non-isotropic piezoelectric materials including the polarization direction and definition of electrodes. The finite element discretization has been done withtwo different types of 3D hexahedral elements: 1) 8 node trilinear elements, 2) 20 node quadratic elements. Theusers are free to choose between these element types for the finite element model of the structure based onhaving preferences for accuracy or computation time. A new method of indexing the elements, nodes and degreesof freedom is introduced to facilitate the definition of loads, boundary conditions, electrodes, etc. The inclusionof piezoelectric material and non-piezoelectric material in the design domain is by default. In comparison to previously published 2D codes, the codes in this paper benefit from the latest advancements in optimizationalgorithms, filtering methods and speedup techniques. The codes are independent and hence can berun without calling any external code. Different parts of the codes are explained in detail to make them comprehensive for newcomers in the field of topology optimization of piezoelectric structures.

The classical Birkhoff–von Neumann (BvN) decomposition expresses a given doubly stochastic matrix as a convex combination of permutation matrices. We investigate the BvN decomposition of symmetric doubly stochastic matrices where the permutation matrices in the decomposition are also symmetric, called SymBvN decomposition.This decomposition is not always possible. Two pioneering theoretical works [Padberg and Wolsey, Math. Program., 29 (1984); Vazirani, arXiv:2010.05984, 2020] establish the conditions under which such a decomposition is possible using graph terminology.We propose a practical algorithm by combining these two works. A simple transformation converts any given symmetric doubly stochastic matrix, with possibly nonzero diagonal elements, to be the adjacency matrix of an edge-weighted undirected graph.The adjacency matrix of the resulting graph admits a SymBvN decomposition if and only if the given matrix does so.The practicality of the proposed algorithm allows us to implement it, release its source code, andreport the first set of experiments ever performed for the SymBvN decomposition.Our experiments suggest that the proposed algorithm is as effective as the state-of-the-art algorithms for the classical BvN decomposition. La décomposition de Birkhoff–von Neumann (BvN) écrit une matrice bistochastique comme une combinaison convexe de matrices de permutation. Nous étudions la décomposition BvN pour des matrices symétriques bistochastiques, en imposant que les matrices de permutation de la décomposition soient aussi symétriques. Cette décomposition est appelée et n'est pas toujours possible. Deux travaux théoriques précurseurs ont établis les conditions sous lesquelles la décomposition est possible pour les matrices d'adjacence d'une classe spéciale de graphes pondérés non-orientés. En s'appuyant sur ces deux travaux, nous proposons un algorithme pratique pour la même classe de matrices.Nous présentons aussi une transformation qui convertit une matrice symétrique bistochastique donnée, ayant possiblement des entrées diagonales non nulles, en la matrice d'adjacence d'un graphe non-orienté. Cette matrice d'adjacence du graphe obtenu admet une décomposition si et seulement si la matrice originale en admet une aussi. Cette transformation et l'aspect pratique de notre algorithme nous permet de proposer la première implémentation d'un algorithme pour la décomposition BvN symétrique de matrices bistochastiques.Munis de cette implémentation, nous expérimentons la décomposition de matrices symétriques bistochastiques en combinaison convexe de matrices de permutation symétriques.Nos expériences indiquent que l'algorithme proposé est aussi efficace que les meilleurs algorithmes connus pour la décomposition BvN classique.

Since Alan Turing envisioned artificial intelligence, technical progress has often been measured by the ability to defeat humans in zero-sum encounters (e.g., Chess, Poker, or Go). Less attention has been given to scenarios in which human–machine cooperation is beneficial but non-trivial, such as scenarios in which human and machine preferences are neither fully aligned nor fully in conflict. Cooperation does not require sheer computational power, but instead is facilitated by intuition, cultural norms, emotions, signals, and pre-evolved dispositions. Here, we develop an algorithm that combines a state-of-the-art reinforcement-learning algorithm with mechanisms for signaling. We show that this algorithm can cooperate with people and other algorithms at levels that rival human cooperation in a variety of two-player repeated stochastic games. These results indicate that general human–machine cooperation is achievable using a non-trivial, but ultimately simple, set of algorithmic mechanisms. Artificial intelligence is now superior to humans in many fully competitive games, such as Chess, Go, and Poker. Here the authors develop a machine-learning algorithm that can cooperate effectively with humans when cooperation is beneficial but nontrivial, something humans are remarkably good at.