Explore the vast range of titles available.

This accessible book provides an introduction to the analysis and design of dynamic multiagent networks. Such networks are of great interest in a wide range of areas in science and engineering, including: mobile sensor networks, distributed robotics such as formation flying and swarming, quantum networks, networked economics, biological synchronization, and social networks. Focusing on graph theoretic methods for the analysis and synthesis of dynamic multiagent networks, the book presents a powerful new formalism and set of tools for networked systems. The book's three sections look at foundations, multiagent networks, and networks as systems. The authors give an overview of important ideas from graph theory, followed by a detailed account of the agreement protocol and its various extensions, including the behavior of the protocol over undirected, directed, switching, and random networks. They cover topics such as formation control, coverage, distributed estimation, social networks, and games over networks. And they explore intriguing aspects of viewing networks as systems, by making these networks amenable to control-theoretic analysis and automatic synthesis, by monitoring their dynamic evolution, and by examining higher-order interaction models in terms of simplicial complexes and their applications. The book will interest graduate students working in systems and control, as well as in computer science and robotics. It will be a standard reference for researchers seeking a self-contained account of system-theoretic aspects of multiagent networks and their wide-ranging applications. This book has been adopted as a textbook at the following universities: University of Stuttgart, GermanyRoyal Institute of Technology, SwedenJohannes Kepler University, AustriaGeorgia Tech, USAUniversity of Washington, USAOhio University, USA

We obtain a complete description of the planar cubic Cayley graphs, providing an explicit presentation and embedding for each of them. This turns out to be a rich class, comprising several infinite families. We obtain counterexamples to conjectures of Mohar, Bonnington and Watkins. Our analysis makes the involved graphs accessible to computation, corroborating a conjecture of Droms.

Let D = ( V , A ) be a digraph of order n , S a subset of V of size k and 2 ≤ k ≤ n . A strong subgraph H of D is called an S - strong subgraph if S ⊆ V ( H ) . A pair of S -strong subgraphs D 1 and D 2 are said to be arc-disjoint if A ( D 1 ) ∩ A ( D 2 ) = ∅ . A pair of arc-disjoint S -strong subgraphs D 1 and D 2 are said to be internally disjoint if V ( D 1 ) ∩ V ( D 2 ) = S . Let κ S ( D ) (resp. λ S ( D ) ) be the maximum number of internally disjoint (resp. arc-disjoint) S -strong subgraphs in D . The strong subgraph k -connectivity is defined as κ k ( D ) = min { κ S ( D ) ∣ S ⊆ V , | S | = k } . As a natural counterpart of the strong subgraph k -connectivity, we introduce the concept of strong subgraph k -arc-connectivity which is defined as λ k ( D ) = min { λ S ( D ) ∣ S ⊆ V ( D ) , | S | = k } . A digraph D = ( V , A ) is called minimally strong subgraph ( k , ℓ ) -(arc-)connected if κ k ( D ) ≥ ℓ (resp. λ k ( D ) ≥ ℓ ) but for any arc e ∈ A , κ k ( D - e ) ≤ ℓ - 1 (resp. λ k ( D - e ) ≤ ℓ - 1 ). In this paper, we first give complexity results for λ k ( D ) , then obtain some sharp bounds for the parameters κ k ( D ) and λ k ( D ) . Finally, minimally strong subgraph ( k , ℓ ) -connected digraphs and minimally strong subgraph ( k , ℓ ) -arc-connected digraphs are studied.

We present a first-order recursive approach to sensitivity analysis based on the application of the direct differentiation method to the inverse Lagrangian dynamics of rigid multibody systems. Our method is simple and efficient and is characterized by the following features. Firstly, it describes the kinematics of multibody systems using branch connectivity graphs and joint-branch connectivity matrices. For most mechanical systems with an open-tree kinematic structure, this method turns out to be more efficient compared to other kinematic descriptions employing joint or link connectivity graphs. Secondly, a recursive sensitivity analysis is presented for a dynamic system with an open-tree kinematic structure and inverse dynamic equations described in terms of the Lagrangian formalism. Thirdly, known approaches to recursive inverse dynamic and sensitivity analyses are modified to include dynamic systems with external forces and torques acting simultaneously at all joints. Finally, the proposed method for sensitivity analysis is easy to implement and computationally efficient. It can be utilized to evaluate the derivatives of the dynamic equations of multibody systems in gradient-based optimization algorithms. It also allows less experienced users to perform sensitivity analyses using the power of high-level programming languages such as MATLAB. To illustrate the method, simulation results for a human body model are discussed. The shortcomings of the method and possible directions for future work are outlined.

The lane graph is critical for applications such as autonomous driving and lane-level route planning. While previous research has focused on extracting lane-level graphs from aerial imagery using convolutional neural networks (CNNs) followed by post-processing segmentation-to-graph algorithms, these methods often face challenges in producing sharp and complete segmentation masks. Challenges such as occlusions, variations in lighting, and changes in road texture can lead to incomplete and inaccurate lane masks, resulting in poor-quality lane graphs. To address these challenges, we propose a novel approach that refines the lane masks, output by a CNN, using diffusion models. Experimental results on a publicly available dataset demonstrate that our method outperforms existing methods based solely on CNNs or diffusion models, particularly in terms of graph connectivity. Our lane mask refinement approach enhances the quality of the extracted lane graph, yielding gains of approximately 1.5% in GEO F1 and 3.5% in TOPO F1 scores over the best-performing CNN-based method, and improvements of 28% and 34%, respectively, compared to a prior diffusion-based approach. Both GEO F1 and TOPO F1 scores are critical metrics for evaluating lane graph quality. Additionally, ablation studies are conducted to evaluate the individual components of our approach, providing insights into their respective contributions and effectiveness.

Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P\\P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2-2⌉-vertex connected, and the bistellar flip graph is (n-3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n-3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2-2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n-3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations.

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics, and threshold phenomena. Recent work on heuristics and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions of Boolean satisfiability problems and establish various dichotomies in Schaefer's framework. On the structural side, we obtain dichotomies for the kinds of subgraphs of the hypercube that can be induced by the solutions of Boolean formulas, as well as for the diameter of the connected components of the solution space. On the computational side, we establish dichotomy theorems for the complexity of the connectivity and $st$-connectivity questions for the graph of solutions of Boolean formulas. Our results assert that the intractable side of the computational dichotomies is PSPACE-complete, while the tractable side--which includes but is not limited to all problems with polynomial-time algorithms for satisfiability--is in P for the $st$-connectivity question, and in coNP for the connectivity question. The diameter of components can be exponential for the PSPACE-complete cases, whereas in all other cases it is linear; thus, diameter and complexity of the connectivity problems are remarkably aligned. The crux of our results is an expressibility theorem showing that in the tractable cases, the subgraphs induced by the solution space possess certain good structural properties, whereas in the intractable cases, the subgraphs can be arbitrary.

This research investigates an efficient strategy for early detection and intervention of attention-deficit hyperactivity disorder (ADHD) in children. ADHD is a neurodevelopmental condition characterized by inattention and hyperactivity/impulsivity symptoms, which can significantly impact a child’s daily life. This study employed two distinct brain functional connectivity measurements to assess our approach across various local graph features. Six common classifiers are employed to distinguish between children with ADHD and healthy control. Based on the phase-based analysis, the study proposes two biomarkers that differentiate children with ADHD from healthy control, with a remarkable accuracy of 99.174%. Our findings suggest that subgraph centrality of phase-lag index brain connectivity within the beta and delta frequency bands could be a promising biomarker for ADHD diagnosis. Additionally, we identify node betweenness centrality of inter-site phase clustering connectivity within the delta and theta bands as another potential biomarker that warrants further exploration. These biomarkers were validated using a t-statistical test and yielded a p-value of under 0.05, which approved their significant difference in these two groups. Suggested biomarkers have the potential to improve the accuracy of ADHD diagnosis and could help identify effective intervention strategies for children with the condition.