检索结果-内蒙古大学图书馆

CkIO: Parallel File Input for Over-Decomposed Task-Based Systems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jacob, Mathew Taylor, Maya Kale, Laxmikant University of Illinois Urbana-Champaign United States

Parallel input performance issues are often neglected in large scale parallel applications in Computational Science and Engineering. Traditionally, there has been less focus on input performance because either input sizes are small (as in biomolecular simulations) or the time doing input is insignificant compared with the simulation with many timesteps. But newer applications, such as graph algorithms add a premium to file input performance. Additionally, over-decomposed systems, such as Charm++/AMPI, present new challenges in this context in comparison to MPI applications. In the over-decomposition model, naive parallel I/O in which every task makes its own I/O request is impractical. Furthermore, load balancing supported by models such as Charm++/AMPI precludes assumption of data contiguity on individual nodes. We develop a new I/O abstraction to address these issues by separating the decomposition of consumers of input data from that of file-reader tasks that interact with the file system. This enables applications to scale the number of consumers of data without impacting I/O behavior or performance. These ideas are implemented in a new input library, CkIO, that is built on Charm++, which is a well-known task-based and overdecomposed-partitions system. CkIO is configurable via multiple parameters (such as the number of file readers and/or their placement) that can be tuned depending on characteristics of the application, such as file size and number of application objects. Additionally, CkIO input allows for capabilities such as effective overlap of input and application-level computation, as well as load balancing and migration. We describe the relevant challenges in understanding file system behavior and architecture, the design alternatives being explored, and preliminary performance data. © 2024, CC BY.

关键词： graph algorithms

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Yu Tan, Zihan National University of Singapore Singapore Rutgers University NJ United States

We study the following distance realization problem. Given a quasi-metric D on a set T of terminals, does there exist a directed Okamura-Seymour graph that realizes D as the (directed) shortest-path distance metric on T? We show that, if we are further given the circular ordering of terminals lying on the boundary, then Monge property is a sufficient and necessary condition. This generalizes previous results for undirected Okamura-Seymour instances. With the circular ordering, we give a greedy algorithm for constructing a directed Okamura-Seymour instance that realizes the input quasi-metric. The algorithm takes the dual perspective concerning flows and routings, and is based on a new way of analyzing graph structures, by viewing graphs as paths and their intersections. We believe this new understanding is of independent interest and will prove useful in other problems in graph theory and graph algorithms. We also design an efficient algorithm for finding such a circular ordering that makes D satisfy Monge property, if one exists. Combined with our result above, this gives an efficient algorithm for the distance realization problem. © 2024, CC BY.

关键词： graph algorithms

On (k, g)-graphs without (g + 1)-Cycles

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Eze, Leonard Chidiebere Jajcay, Robert Jooken, Jorik Department of Algebra and Geometry Faculty of Mathematics Physics and Informatics Mlynská dolina Bratislava842 48 Slovakia Department of Computer Science KU Leuven Kulak Kortrijk8500 Belgium

A (k, g, g + 1)-graph is a k-regular graph of girth g which does not contain cycles of length g + 1. Such graphs are known to exist for all parameter pairs k ≥ 3, g ≥ 3, and we focus on determining the orders n(k, g, g + 1) of the smallest (k, g, g + 1)-graphs. This problem can be viewed as a special case of the previously studied Girth-Pair Problem, the problem of finding the order of a smallest k-regular graph in which the length of a smallest even length cycle and the length of a smallest odd length cycle are prescribed. When considering the case of an odd girth g, this problem also yields results towards the Cage Problem, the problem of finding the order of a smallest k-regular graph of girth g. We establish the monotonicity of the function n(k, g, g + 1) with respect to increasing g, and present universal lower bounds for the values n(k, g, g + 1). We propose an algorithm for generating all (k, g, g + 1)-graphs on n vertices, use this algorithm to determine several of the smaller values n(k, g, g + 1), and discuss various approaches to finding smallest (k, g, g + 1)-graphs within several classes of highly symmetrical graphs. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms

Size Should not Matter: Scale-invariant Stress Metrics

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ahmed, Reyan Erten, Cesim Kobourov, Stephen Lotz, Jonah Miller, Jacob Taraz, Hamlet

The normalized stress metric measures how closely distances between vertices in a graph drawing match the graph-theoretic distances between those vertices. It is one of the most widely employed quality metrics for graph drawing, and is even the optimization goal of several popular graph layout algorithms. However, normalized stress can be misleading when used to compare the outputs of two or more algorithms, as it is sensitive to the size of the drawing compared to the graph-theoretic distances used. Uniformly scaling a layout will change the value of stress despite not meaningfully changing the drawing. In fact, the change in stress values can be so significant that a clearly better layout can appear to have a worse stress score than a random layout. In this paper, we study different variants for calculating stress used in the literature (raw stress, normalized stress, etc.) and show that many of them are affected by this problem, which threatens the validity of experiments that compare the quality of one algorithm to that of another. We then experimentally justify one of the stress calculation variants, scale-normalized stress, as one that fairly compares drawing outputs regardless of their size. We also describe an efficient computation for scale-normalized stress and provide an open source implementation. © 2024, CC BY.

关键词： graph algorithms

The Upper Clique Transversal Problem

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Milanič, Martin Uno, Yushi FAMNIT and IAM University of Primorska Koper Slovenia Graduate School of Informatics Osaka Metropolitan University Sakai Osaka Japan

A clique transversal in a graph is a set of vertices intersecting all maximal cliques. The problem of determining the minimum size of a clique transversal has received considerable attention in the literature. In this paper, we initiate the study of the "upper" variant of this parameter, the upper clique transversal number, defined as the maximum size of a minimal clique transversal. We investigate this parameter from the algorithmic and complexity points of view, with a focus on various graph classes. We show that the corresponding decision problem is NP-complete in the classes of chordal graphs, chordal bipartite graphs, cubic planar bipartite graphs, and line graphs of bipartite graphs, but solvable in linear time in the classes of split graphs, proper interval graphs, and cographs, and in polynomial time for graphs of bounded *** Codes 05C69 (Primary), 05C85, 05C75, 05C76, 68Q25, 68R10 (Secondary) © 2023, CC BY.

关键词： graph algorithms

Decremental Matching in General graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Assadi, Sepehr Bernstein, Aaron Dudeja, Aditi Rutgers University United States

We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph G, while the adversary makes changes to the edges of the graph. The goal is to maintain a (1 + ϵ)-approximate maximum matching for constant ϵ > 0, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see [GP13]) gave an algorithm for this problem with an update time of O(√m/ϵ2). Motivated by the fact that the Oϵ(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [HKNS15];Kopelowitz, Pettie, and Porat [KPP16]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [BGS20]) gave an O(poly(log n/ϵ)) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs. In this paper, we bridge the gap between bipartite and general graphs, by giving an Oϵ(poly(log n)) update time algorithm that maintains a (1 + ϵ)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [GLS+19] who give an Oϵ(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching. Copyright © 2022, The Authors. All rights reserved.

关键词： graph algorithms

Sufficient conditions for matching extendability in terms of the Zeroth-order General Randić Index

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Wang, Shuai Su, Guifu College of Mathematics and Physics Beijing University of Chemical Technology Beijing100029 China

Topological indices are important bridge between graph theory and chemical applications. The study of graph matching expandability has been an influential topic in recent research on graph structure. In this paper, we provide some sufficient conditions for a graph to be k-extendable graphs, n-factor-critical graphs and (n, k, d)-graphs and graphs with prefect matching in terms of a significant type of Topological index: the Zeroth-order General Randić Index (α ≥ −1 and α, 0). Copyright © 2023, The Authors. All rights reserved.

关键词： graph algorithms

Flexible realizations existence: NP-completeness on sparse graphs and algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Laštovička, Petr Legerský, Jan Faculty of Information technology Czech Technical University in Prague Czech Republic

One of the questions in Rigidity Theory is whether a realization of the vertices of a graph in the plane is flexible, namely, if it allows a continuous deformation preserving the edge lengths. A flexible realization of a connected graph in the plane exists if and only if the graph has a so called NAC-coloring, which is surjective edge coloring by two colors such that for each cycle either all the edges have the same color or there are at least two edges of each color. The question whether a graph has a NAC-coloring, and hence also the existence of a flexible realization, has been proven to be NP-complete. We show that this question is also NP-complete on graphs with maximum degree five and on graphs with the average degree at most 4 + Ε for every fixed Ε > 0. The existence of a NAC-coloring is fixed parameter tractable when parametrized by treewidth. Since the only existing implementation of checking the existence of a NAC-coloring is rather naive, we propose new algorithms along with their implementation, which is significantly faster. We also focus on searching all NAC-colorings of a graph, since they provide useful information about its possible flexible *** Codes 52C25, 52-04, 68Q25 © 2024, CC BY.

关键词： graph algorithms

ON COMPLEXITY OF ALTERNATING LINK EQUIVALENCE

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Haider, Touseef Tsvietkova, Anastasiia Department of Mathematics and Computer Science Rutgers University Newark 101 Warren Street NewarkNJ07102 United States

Link equivalence up to isotopy in a 3-space is the problem that lies at the root of knot theory, and is important in 3-dimensional topology and geometry. We consider its restriction to alternating links, given by two alternating diagrams with n1 and n2 crossings, and show that this problem has polynomial algorithm in terms of max{n1,n2}. For the proof, we use Tait flyping conjectures, observations from the work of Lackenby, Menasco, Sundberg and Thistlethwaite on alternating links, and algorithmic complexity of some problems from graph theory and topological graph *** Codes 57K10 Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms