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

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Hébert-Johnson, Úrsula Lokshtanov, Daniel University of California Santa BarbaraCA United States

ISBN: (纸本)9783959773652

We design an algorithm that generates an n-vertex unlabeled chordal graph uniformly at random in expected polynomial time. Along the way, we develop the following two results: (1) an FPT algorithm for counting and sampling labeled chordal graphs with a given automorphism π, parameterized by the number of moved points of π, and (2) a proof that the probability that a random n-vertex labeled chordal graph has a given automorphism π ∈ Sn is at most 1/2c max{µ2,n}, where µ is the number of moved points of π and c is a constant. Our algorithm for sampling unlabeled chordal graphs calls the aforementioned FPT algorithm as a black box with potentially large values of the parameter µ, but the probability of calling this algorithm with a large value of µ is exponentially small. © Úrsula Hébert-Johnson and Daniel Lokshtanov.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing graph Hyperbolicity Using Dominating Sets

Computing Graph Hyperbolicity Using Dominating Sets

引用

Symposium on Algorithm Engineering and Experiments (ALENEX)

作者： Coudert, David Nusser, Andre Viennot, Laurent Univ Cote dAzur I3S CNRS INRIA Nice France Saarbrucken Grad Sch Comp Sci Saarland Informat Campus Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Paris Univ Irif CNRS INRIA Paris France

ISBN: (纸本)9781611977042

Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning all quadruples of the graph or using fast matrix multiplication as building block, both are not practical for large graphs. In this paper, we propose and evaluate an approach that uses a hierarchy of distance-k dominating sets to reduce the search space. This technique, compared to the previous best practical algorithms, enables us to compute the hyperbolicity of graphs with unprecedented size (up to a million nodes).

关键词： Gromov hyperbolicity graph algorithms algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

graph Summarization: Compactness Meets Efficiency

引用

Proceedings of the ACM on Management of Data 2024年第3期2卷 1-26页

作者： Deming Chu Fan Zhang Wenjie Zhang Ying Zhang Xuemin Lin University of New South Wales Sydney NSW Australia Guangzhou University Guangzhou Guangdong China University of Technology Sydney Sydney NSW Australia Shanghai Jiao Tong University Shanghai China

As the volume and ubiquity of graphs increase, a compact graph representation becomes essential for enabling efficient storage, transfer, and processing of graphs. Given a graph, the graph summarization problem asks for a compact representation that consists of a summary graph and the corrections, such that we can recreate the original graph from the representation exactly. Although this problem has been studied extensively, the existing works either trade summary compactness for efficiency, or vice versa. In particular, a well-known greedy method provides the most compact summary but incurs prohibitive time cost, while the state-of-the-art algorithms with practical overheads are more than 20% behind in summary compactness in our comparison with the greedy *** paper presents Mags and Mags-DM, two algorithms that aim to bridge the compactness and efficiency in graph summarization. Mags adopts the existing greedy paradigm that provides state-of-the-art compactness, but significantly improves its efficiency with a novel algorithm design. Meanwhile, Mags-DM follows a different paradigm with practical efficiency and overcomes its limitations in compactness. Moreover, both algorithms can support parallel computing environments. We evaluate Mags and Mags-DM on graphs up to billion-scale and demonstrate that they achieve state-of-the-art in both compactness and efficiency, rather than in one of them. Compared with the method that offers state-of-the-art compactness, Mags and Mags-DM have a small difference (< 0.1% and < 2.1%) in compactness. For efficiency, Mags is on average 11.1x and 4.2x faster than the two state-of-the-art algorithms with practical overheads, while Mags-DM can further reduce the running time by 13.4x compared with Mags. This shows that graph summarization algorithms can be made practical while still offering a compact summary.

关键词： graph algorithms graph summarization massive graphs

来源：评论

学校读者我要写书评

暂无评论

Revisiting Local Computation of PageRank: Simple and Optimal 2024

Revisiting Local Computation of PageRank: Simple and Optimal

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Wang, Hanzhi Wei, Zhewei Wen, Ji-Rong Yang, Mingji Renmin Univ China Beijing Peoples R China

ISBN: (纸本)9798400703836

We revisit ApproxContributions, the classic local graph exploration algorithm proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng (WAW 07, Internet Math. 08) for computing an epsilon-approximation of the PageRank contribution vector for a target node t on a graph with n nodes and m edges. We give a worst-case complexity bound of it as O(n Pi(t)/epsilon center dot min(Delta(in),Delta(out),root m)), where Pi(t) is the PageRank score of t, and Delta(in) and Delta(out) are the maximum in-degree and out-degree of the graph, resp. We also give a lower bound of Omega(min(Delta(in)/delta,Delta(out)/delta,root m/delta,m)) for detecting ts delta-contributing set, showing that the simple ApproxContributions algorithm is already optimal. As ApproxContributions has become a cornerstone for computing random-walk probabilities, our results and techniques can be applied to derive better bounds for various relevant problems. In particular, we investigate the computational complexity of locally estimating a nodes PageRank centrality. We improve the best-known upper bound of (O) over tilde (n(2/3)center dot min(Delta(1/3)(out),m(1/6))) given by Bressan, Peserico, and Pretto (SICOMP 23) to O(n(1/2)center dot min(Delta(1/2)(in),Delta(1/2)(out),m(1/4))) by combining ApproxContributions with Monte Carlo sampling. We also improve their lower bound of Omega(min(n(1/2)Delta(1/2)(out),n(1/3)m(1/3))) to Omega(n(1/2)center dot min(Delta(1/2)(in),Delta(1/2)(out),m(1/4))) if min(Delta(in),Delta(out))=Omega(n(1/3)), and to Omega(n(1/2-gamma)(min(Delta(in),Delta(out)))(1/2+gamma)) otherwise, where gamma > 0 is an arbitrarily small constant. Our matching upper and lower bounds resolve the open problem of whether one can tighten the bounds given by Bressan, Peserico, and Pretto (FOCS 18, SICOMP 23). Remarkably, the techniques and analyses for proving all our results are surprisingly simple.

关键词： graph algorithms sublinear algorithms PageRank random walks

来源：评论

学校读者我要写书评

暂无评论

Spanning Adjacency Oracles in Sublinear Time 15

Spanning Adjacency Oracles in Sublinear Time

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Bodwin, Greg Fleischmann, Henry Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Univ Cambridge Dept Pure Math & Math Stat Cambridge England

ISBN: (纸本)9783959773096

Suppose we are given an n-node, m-edge input graph G, and the goal is to compute a spanning subgraph H on O(n) edges. This can be achieved in linear O(m + n) time via breadth-first search. But can we hope for sublinear runtime in some range of parameters - for example, perhaps O(n(1.9)) worst-case runtime, even when the input graph has n(2) edges? If the goal is to return H as an adjacency list, there are simple lower bounds showing that Omega(m + n) runtime is necessary. If the goal is to return H as an adjacency matrix, then we need Omega(n(2)) time just to write down the entries of the output matrix. However, we show that neither of these lower bounds still apply if instead the goal is to return H as an implicit adjacency matrix, which we call an adjacency oracle. An adjacency oracle is a data structure that gives a user the illusion that an adjacency matrix has been computed: it accepts edge queries (u, v), and it returns in near-constant time a bit indicating whether or not (u, v)is an element of E(H). Our main result is that, for any 0 < epsilon < 1, one can construct an adjacency oracle for a spanning subgraph on at most (1 + epsilon) n edges, in (O) over tilde (n epsilon(-1)) time (hence sublinear time on input graphs with m >> n edges), and that this construction time is near-optimal. Additional results include constructions of adjacency oracles for k-connectivity certificates and spanners, which are similarly sublinear on dense-enough input graphs. Our adjacency oracles are closely related to Local Computation algorithms (LCAs) for graph sparsifiers;they can be viewed as LCAs with some computation moved to a preprocessing step, in order to speed up queries. Our oracles imply the first LCAs for computing sparse spanning subgraphs of general input graphs in (O) over tilde (n) query time, which works by constructing our adjacency oracle, querying it once, and then throwing the rest of the oracle away. This addresses an open problem of Rubinfeld [CSR '17].

关键词： graph algorithms Sublinear algorithms Data structures graph theory

来源：评论

学校读者我要写书评

暂无评论

VICAN: Very Efficient Calibration Algorithm for Large Camera Networks

VICAN: Very Efficient Calibration Algorithm for Large Camera...

引用

IEEE International Conference on Robotics and Automation (ICRA)

作者： Moreira, Gabriel Marques, Manuel Costeira, Jodo Paulo Hauptman, Alexander Carnegie Mellon Univ Sch Comp Sci Language Technol Inst Pittsburgh PA 15213 USA Inst Super Tecn Inst Syst & Robot Lisbon Portugal

ISBN: (纸本)9798350384581;9798350384574

The precise estimation of camera poses within large camera networks is a foundational problem in computer vision and robotics, with broad applications spanning autonomous navigation, surveillance, and augmented reality. In this paper, we introduce a novel methodology that extends state-of-the-art Pose graph Optimization (PGO) techniques. Departing from the conventional PGO paradigm, which primarily relies on camera-camera edges, our approach centers on the introduction of a dynamic element - any rigid object free to move in the scene - whose pose can be reliably inferred from a single image. Specifically, we consider the bipartite graph encompassing cameras, object poses evolving dynamically, and camera-object relative transformations at each time step. This shift not only offers a solution to the challenges encountered in directly estimating relative poses between cameras, particularly in adverse environments, but also leverages the inclusion of numerous object poses to ameliorate and integrate errors, resulting in accurate camera pose estimates. Though our framework retains compatibility with traditional PGO solvers, its efficacy benefits from a custom-tailored optimization scheme. To this end, we introduce an iterative primal-dual algorithm, capable of handling large graphs. Empirical benchmarks, conducted on a new dataset of simulated indoor environments, substantiate the efficacy and efficiency of our approach.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The lattice of cycles of an undirected graph

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2021年 611卷 213-236页

作者： Averkov, G. Chavez, A. De Loera, J. A. Gillespie, B. BTU Cottbus Senftenberg Fak 1 Cottbus Germany Univ Calif Davis Dept Math Davis CA 95616 USA Colorado State Univ Dept Math Ft Collins CO 80523 USA

We study bases of the lattice generated by the cycles of an undirected graph, defined as the integer linear combinations of the 0/1-incidence vectors of cycles. We prove structural results for this lattice, including explicit formulas for its dimension and determinant, and we present efficient algorithms to construct lattice bases, using only cycles as generators, in quadratic time. By algebraic considerations, we relate these results to the more general setting with coefficients from an arbitrary Abelian group. Our results generalize classical results for the vector space of cycles of a graph over the binary field to the case of an arbitrary field. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Undirected graphs graph cycles Cycle lattice Lattice basis Linear hull Abelian group graph algorithms Algorithmic complexity

来源：评论

学校读者我要写书评

暂无评论

Geometric Spanners: New algorithms and Frameworks

Geometric Spanners: New Algorithms and Frameworks

引用

作者： Khodabandeh, Hadi University of California Irvine

学位级别：Ph.D., Doctor of Philosophy

In this dissertation, we investigate a multitude of novel algorithms aimed at efficiently constructing geometric spanners across various computational scenarios. In addition to devising new algorithms, we also develop several methodologies and frameworks for analyzing geometric spanners and their attributes, such as sparsity, weight, and separation properties, offering valuable tools for readers engaged in related research *** present our results in three main chapters. We begin by investigating the construction of the greedy $t$-spanner for a set of points in the plane. This spanner is an undirected graph constructed by considering pairs of points in order by distance, and connecting a pair by an edge when there does not already exist a path connecting that pair with length at most $t$ times the Euclidean distance. Our analysis reveals that for any t > 1, these graphs exhibit a linear number of crossings and possess bounded degeneracy in their intersection graphs. These properties lead to the development of a separator theorem for greedy spanners, which demonstrates our capability to form a recursive separator hierarchy from the planarizations of these spanners in linear time, or in near-linear time if the planarization is unknown. Expanding on these fundamental concepts, we address an unresolved question concerning the existence of lightweight bounded-degree spanners for unit ball graphs in metrics with bounded doubling dimension. We present a distributed algorithm operating within O (log*n) rounds in the LOCAL model of computation, achieving significant improvements over prior methodologies. We extend the applicability of this algorithm to the CONGEST model while maintaining its round complexity. Our investigations extend to the two-dimensional Euclidean plane, where we devise constructions with a constant average number of edge intersections per node. Experimental evaluations validate the efficiency of our distributed algorithm compared to centralized count

关键词： Computational geometry Geometric spanners graph algorithms Theoretical computer science

来源：评论

学校读者我要写书评

暂无评论

Combinatorics in AI: Principles & algorithms An Extended Abstract

Combinatorics in AI: Principles & Algorithms An Extended Abs...

引用

2024 IEEE International Conferences of AI, Science, Engineering, and Technology, AIxSET 2024

作者： Barr, Joseph R. Haass, Jon C Shaw, Peter Abu-Khzam, Faisal N. Embry-Riddle Aeronautical University United States Oujiang Laboratory Zhejiang Wenzhou China Lebanese American University Dept. of Comp. Sc. & Mathematics Lebanon

ISBN: (纸本)9798350390995

Therein we describe a few cases where combinatorics appears in machine learning. The fundamental problem of learning is intimately connected to combinatorial geometry. The geometric invariant Vapnik-Chvronenkis dimension or VC-dimension [13], plays a crucial role in the analysis of machine learning procedures especially the suitability of an algorithm to shatter a set of labeled examples. The notion that data is represented as a correlation matrix becomes practical when regarded as a graph on which graph algorithms are used to extract information about the underlying data. algorithms which partition a graph are, in fact, stratification procedures of the underlying data. Yet another combinatorial application to statistical models involve selecting a subset of variables 'variable selection' used in linearized models like the ubiquitous logistic regression, or Cox partial likelihood models. Those techniques are particularly useful in modeling with genomics data which tend to be high dimensional. Indeed, the number of genes under study is typically in the thousands while in clinical trials the number of subjects under study may be rather small, possibly in the hundreds. Having thousands of features and only a few hundreds of subjects poses difficult modeling challenges. Feature selection methods work well when there are far fewer features than examples and statistical feature selection methods do not seem to work well in such extreme cases. Combinatorial methods embedded in a workflow help alleviate the problem by eliminating redundant inputs. We demonstrate how combinatorial algorithms, which extract useful information from the matrix of pairwise correlations are used in feature selection. In fact, we show how computing special variants of what is known as 'maximal independent set' could help solve intractable statistical modeling problems where classical selection methods are confounded by excessively larger feature sizes. © 2024 IEEE.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Sparse graphic Degree Sequences Have Planar Realizations 49

Sparse Graphic Degree Sequences Have Planar Realizations

引用

49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024

作者： Bar-Noy, Amotz Böhnlein, Toni Peleg, David Ran, Yingli Rawitz, Dror NY United States Huawei Zurich Switzerland Weizmann Institute of Science Rehovot Israel Bar Ilan University Ramat-Gan Israel

ISBN: (纸本)9783959773355

A sequence d = (d1, d2, . . ., dn) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n − 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n − 4 − 2ω1, where ω1 is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n − 2ω1 that are non-planaric. For the case ω1 = 0, we show that d is planaric when ∑ d ≤ 4n − 4. Conversely, we show that there is a graphic sequence with ∑ d = 4n − 2 that is non-planaric. In fact, when ∑ d ≤ 4n − 6 − 2ω1, d can be realized by a graph with a 2-page book embedding. © Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：