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

18th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Suzuki, Takahiro Kimura, Kei Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Japan Kyushu Univ Fac Informat Sci & Elect Engn Fukuoka Japan

ISBN: (纸本)9789819723393;9789819723409

Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset A(0) of G is a target set if eventually all vertices in G are activated by initially activating vertices of A(0). The Target Set Selection problem (TSS) involves finding the smallest target set of G with vertex thresholds. This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem (WTSS) from the perspective of parameterized complexity. Let k be the solution size and l be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by k + l, and W[2]-hard for cographs when parameterized by k. We also prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k. On the other hand, we show that WTSS can be solved in O(n log n) time for complete graphs. Additionally, we design FPT algorithms for WTSS when parameterized by nd + l, tw + l, ce, and vc, where nd is the neighborhood diversity, tw is the treewidth, ce is the cluster editing number, and VC is the vertex cover number of the input graph.

关键词： Parameterized complexity graph algorithms Target set selection

来源：评论

学校读者我要写书评

暂无评论

Approximating Single-Source Personalized PageRank with Absolute Error Guarantees 27

Approximating Single-Source Personalized PageRank with Absol...

引用

27th International Conference on Database Theory (ICDT)

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

ISBN: (纸本)9783959773126

Personalized PageRank (PPR) is an extensively studied and applied node proximity measure in graphs. For a pair of nodes s and t on a graph G = (V, E), the PPR value pi(s, t) is defined as the probability that an alpha-discounted random walk from s terminates at t, where the walk terminates with probability a at each step. We study the classic Single-Source PPR query, which asks for PPR approximations from a given source node s to all nodes in the graph. Specifically, we aim to provide approximations with absolute error guarantees, ensuring that the resultant PPR estimates (pi) over cap (s, t) satisfy max (t is an element of V)vertical bar vertical bar(pi) over cap (s, t)-pi(s, t)<= epsilon for a given error bound epsilon. We propose an algorithm that achieves this with high probability, with an expected running time of (O) over tilde directed graphs(2), where m = |E|;(O) over tilde(root d(max)/epsilon for undirected graphs, where d(max) is the maximum node degree in the graph;(O) over tilde (n(gamma-1/2)/epsilon) for power-law graphs, where n = |V | and gamma is an element of(1/2, 1) is the extent of the power law. These sublinear bounds improve upon existing results. We also study the case when degree-normalized absolute error guarantees are desired, requiring max(t is an element of V) vertical bar(pi) over cap /d(t) - pi (s, t)/ d(t)vertical bar <= epsilon(d) for a given error bound epsilon(d), where the graph is undirected and d(t) is the degree of node t. We give an algorithm that provides this error guarantee with high probability, achieving an expected complexity of e (O) over tilde root Sigma t is an element of V pi (s,t)/ d(t)/epsilon(d). This improves over the previously known O(1/ ed) complexity.

关键词： graph algorithms Sublinear algorithms Personalized PageRank

来源：评论

学校读者我要写书评

暂无评论

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques 2024

Towards Optimal Output-Sensitive Clique Listing or: Listing ...

引用

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

作者： Dalirrooyfard, Mina Mathialagan, Surya Williams, Virginia Vassilevska Xu, Yinzhan Morgan Stanley Res Calgary AB Canada MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9798400703836

We study the problem of finding and listing k-cliques in an m-edge, n-vertex graph, for constant k >= 3. This is a fundamental problem of both theoretical and practical importance. Our first contribution is an algorithmic framework for finding k-cliques that gives the first improvement in 19 years over the old runtimes for 4 and 5-clique finding, as a function of m [Eisenbrand and Grandoni, TCS04]. With the current bounds on matrix multiplication, our algorithms run in O(m(1.66)) and O(m(2.06)) time, respectively, for 4-clique and 5-clique finding. Our main contribution is an output-sensitive algorithm for listing k-cliques, for any constant k >= 3. We complement the algorithm with tight lower bounds based on standard fine-grained assumptions. Previously, the only known conditionally optimal output-sensitive algorithms were for the case of 3-cliques given by Bj'orklund, Pagh, Vassilevska W. and Zwick [ICALP14]. If the matrix multiplication exponent omega is 2, and if the number of k-cliques t is large enough, the running time of our algorithms is (O) over tilde (min{m(1/k-2)t(1 - 2/k(k-2)),n(2/k-1)t(1-2/k(k-1))}), and this is tight under the Exact-k-Clique Hypothesis. This running time naturally extends the running time obtained by Bjorklund, Pagh, Vassilevska W. and Zwick for k=3. Our framework is very general in that it gives k-clique listing algorithms whose running times can be measured in terms of the number of l-cliques Delta(l) in the graph for any 1 <= l < k. This generalizes the typical parameterization in terms of n (the number of 1-cliques) and m (the number of 2-cliques). If omega is 2, and if the size of the output, Delta(k), is sufficiently large, then for every l < k, the running time of our algorithm for listing k-cliques is (O) over tilde(Delta(2/l (k - l))(l)Delta(1-2/k(k-l))(k)). We also show that this runtime is optimal for all 1 <= l < k under the Exact k-Clique hypothesis.

关键词： cliques graph algorithms fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

Parallel Peeling of Bipartite Networks for Hierarchical Dense Subgraph Discovery

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2023年第2期10卷 1-35页

作者： Lakhotia, Kartik Kannan, Rajgopal Prasanna, Viktor Univ Southern Calif Los Angeles CA 90007 USA US Army Res Lab Adelphi MD USA

Wing and Tip decomposition are motif-based analytics for bipartite graphs that construct a hierarchy of butterfly (2,2-biclique) dense edge and vertex induced subgraphs, respectively. They have applications in several domains, including e-commerce, recommendation systems, document analysis, and others. Existing decomposition algorithms use a bottom-up approach that constructs the hierarchy in an increasing order of the subgraph density. They iteratively select the edges or vertices with minimum butterfly count peel, i.e., remove them along with their butterflies. The amount of butterflies in real-world bipartite graphs makes bottom-up peeling computationally demanding. Furthermore, the strict order of peeling entities results in a large number of sequentially dependent iterations. Consequently, parallel algorithms based on bottom up peeling incur heavy synchronization and poor scalability. In this article, we propose a novel Parallel Bipartite Network peelinG (PBNG) framework that adopts a two-phased peeling approach to relax the order of peeling, and in turn, dramatically reduce synchronization. The first phase divides the decomposition hierarchy into few partitions and requires little synchronization. The second phase concurrently processes all partitions to generate individual levels of the hierarchy and requires no global synchronization. The two-phased peeling further enables batching optimizations that dramatically improve the computational efficiency of PBNG. We empirically evaluate PBNG using several real-world bipartite graphs and demonstrate radical improvements over the existing approaches. On a shared-memory 36 core server, PBNG achieves up to 19.7x self-relative parallel speedup. Compared to the state-of-the-art parallel framework PARBUTTERFLY, PBNG reduces synchronization by up to 15, 260x and execution time by up to 295x. Furthermore, it achieves up to 38.5x speedup over state-of-the-art algorithms specifically tuned for wing decomposition. Our source

关键词： graph algorithms parallel graph analytics dense graph mining bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

algorithms for computing chromatic polynomials and chromatic index polynomials

引用

SCIENTIFIC AFRICAN 2024年 24卷

作者： Hordofa, Lateram Zawuga Repalle, V. N. SrinivasaRao Ashebo, Mamo Abebe Wollega Univ Dept Math Post Box 395 Nekemte Ethiopia

Objectives: The aim of this article is to enhance the understanding of the computation of chromatic polynomials and chromatic index polynomials, and to facilitate their practical use in various fields by demonstrating and supporting the proposed algorithms. Results: The theorems for computing the chromatic polynomial and chromatic index polynomial are thoroughly demonstrated and validated in this article. Additionally, the algorithms used in these computations are introduced and explained.

关键词： graph algorithms Chromatic index polynomial Chromatic polynomial

来源：评论

学校读者我要写书评

暂无评论

A Fully Physics-Based CMOS Camera Model Within a 3-D Virtual World Ray Trace Simulation Engine

引用

SN Computer Science 2024年第1期5卷 61页

作者： Pecharromán-Gallego, Raúl Ibeo Automotive Eindhoven B.V. High Tech Campus 69 Eindhoven 5656 AG Netherlands

CMOS based cameras are present nowadays for many imaging applications, ranging from any consumer, industrial or artistic use, they will also be introduced into the simulation engines applied to any raytracing technology, like electro optical, radar or LiDAR sensors simulation in the automotive industry, which is the scope of this work, that introduces a holistic model of CMOS camera that can be customized for different applications from input specifications. Starting with a ray trace simulation environment of the surrounding scene to its light reaching the lens, to photon conversion into electron–hole pairs within the image sensor photodiodes, to final image rendering and shown in display. Both the camera model and the ray tracing engine are fully physics-based. The whole system is validated within a simulated environmental illumination system including the camera sensor pipeline for final image processing. We also use industrial standard color and resolution targets and methodologies for image quality validation. Furthermore, a HDR image fusion by using fusion of images captured at different exposure values is also introduced. Moreover, validation against real photographs on color targets and the resolution methodologies introduced here leads to feasibility of the whole process presented. In summary, this work presents a number of well proven methodologies on CMOS camera simulation valid within both a ray trace environment and real world, and its automotive application feasibility supported with full real measurements validation. © 2023, The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd.

关键词： CMOS sensor simulation graph algorithms Image processing and computer vision Image quality Model validation Raytracing

来源：评论

学校读者我要写书评

暂无评论

A Robust Network Model for Studying Microbiomes in Precision Agriculture Applications 24th

A Robust Network Model for Studying Microbiomes in Precision...

引用

24th International Conference on Computational Science (ICCS)

作者： Kim, Suyeon Thapa, Ishwor Ali, Hesham H. Univ Nebraska Coll Informat Sci & Technol Omaha NE 68182 USA

ISBN: (纸本)9783031637773;9783031637780

Recent rapid advancements in high-throughput sequencing technologies have made it possible for researchers to explore the microbial universe in high degrees of depth that were not possible even few years ago. Microbial communities occupy numerous environments everywhere and significantly impact the health of the living organisms in their environments. With the availability of microbiome data, advanced computational tools are critical to conduct the needed analysis and allow researchers to extract meaningful knowledge leading to actionable decisions. However, despite many attempts to develop tools to analyze the heterogeneous datasets associated with various microbiomes, such attempts lack the sophistication and robustness needed to efficiently analyze these complex heterogeneous datasets and produce accurate results. In addition, almost all current methods employ heuristic concepts that do not guarantee the robustness and reproducibility needed to provide the biomedical community with trusted analysis that lead to precise data-driven decisions. In this study, we present a network model that attempts to overcome these challenges by utilizing graph-theoretic concepts and employing multiple computational methods with the goal of conducting robust analysis and produce accurate results. To test the proposed model, we performed the analysis on plant microbiome datasets to obtain distinctive functional modules based on key microbial interrelationships in a given host environment. Our findings establish a framework for a new understanding of the association between functional modules based on microbial community structure.

关键词： Precision agriculture plant microbiomes robust analysis network models graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Knapsack: Connectedness, Path, and Shortest-Path 16th

Knapsack: Connectedness, Path, and Shortest-Path

引用

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Dey, Palash Kolay, Sudeshna Singh, Sipra Indian Inst Technol Kharagpur Kharagpur W Bengal India

ISBN: (纸本)9783031556005;9783031556012

We study the KNAPSACK problem with graph-theoretic constraints. That is, there exists a graph structure on the input set of items of KNAPSACK and the solution also needs to satisfy certain graph theoretic properties on top of the KNAPSACK constraints. In particular, we study CONNECTED KNAPSACK where the solution must be a connected subset of items which has maximum value and satisfies the size constraint of the knapsack. We show that this problem is strongly NP-complete even for graphs of maximum degree four and NP-complete even for star graphs. On the other hand, we develop an algorithm running in time O (2(O(tw log tw)) . poly(n) min{s(2), d(2)}) where tw, s, d, n are respectively treewidth of the graph, the size of the knapsack, the target value of the knapsack, and the number of items. We also exhibit a (1- epsilon) factor approximation algorithm running in time O (2(O(tw log tw)) . poly( n, 1/epsilon)) for every epsilon > 0. We show similar results for PATH KNAPSACK and Shortest PATH KNAPSACK, where the solution must also induce a path and shortest path, respectively. Our results suggest that CONNECTED KNAPSACK is computationally the hardest, followed by PATH KNAPSACK and then SHORTEST PATH KNAPSACK.

关键词： Knapsack graph algorithms Parameterised Complexity Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Framework for Parallelizing Approximate Gaussian Elimination 24

A Framework for Parallelizing Approximate Gaussian Eliminati...

引用

36th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Baumann, Yves Kyng, Rasmus Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9798400704161

In a breakthrough result, Spielman and Teng (2004) developed a nearly-linear time solver for Laplacian linear equations, i.e. equations where the coefficient matrix is symmetric with non-negative diagonals and zero rowsums. Since the development of the Spielman-Teng solver, there has been substantial progress, simplifying and improving their result, but obtaining a fast practical, parallel Laplacian solver remains an open problem. We present a framework for obtaining extremely simple, parallel Laplacian linear equation solvers with nearly-linear work and sub-linear depth. Our framework allows us to parallelize any Laplacian solver based on repeated single-vertex approximate Gaussian elimination. We demonstrate this by parallelizing both the algorithm of Kyng and Sachdeva (2016) and the practical variant by Gao, Kyng, and Spielman (2023). Our framework is work-efficient in the sense of matching the sequential work of these algorithms. Our parallelization framework is very simple: We sample a subset of the current low-degree vertices (sparse columns), and in parallel we eliminate all vertices that are isolated in the resulting induced subgraph. This approach can be combined with any parallelizable approximate single-vertex elimination subroutine with sparse output. Given the simplicity of the approach, we believe that using it to parallelize the solver of Gao, Kyng, and Spielman (2023) is the most promising direction for obtaining practical parallel Laplacian solvers. If we additionally use a parallel spectral sparsification routine, our approach can be modified to work in polylogarithmic depth and nearly-linear work.

关键词： Approximate Gaussian Elimination Laplacian Linear System Solver Parallel algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

New Structures and algorithms for Length-Constrained Expander Decompositions 65

New Structures and Algorithms for Length-Constrained Expande...

引用

65th Symposium on Foundations of Computer Science

作者： Haeupler, Bernhard Hershkowitz, D. Ellis Tan, Zihan Univ Sofia St Kliment Ohridski INSAIT Sofia Bulgaria Swiss Fed Inst Technol Zurich Switzerland Brown Univ Providence RI 02912 USA Rutgers State Univ New Brunswick NJ USA

ISBN: (纸本)9798331516758;9798331516741

Expander decompositions form the basis of one of the most flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this paradigm to better work for problems with lengths, distances and costs. Roughly, an (h, s)-length phi-expander decomposition is a small collection of length increases to a graph so that nodes within distance h can route flow over paths of length hs with congestion at most 1/phi. In this work, we give a close-to-linear time algorithm for computing length-constrained expander decompositions in graphs with general lengths and capacities. Notably, and unlike previous works, our algorithm allows for one to trade off off between the size of the decomposition and the length of routing paths: for any epsilon > 0 not too small, our algorithm computes in close-to-linear time an (h, s)-length phi-expander decomposition of size m . phi . n(epsilon) where s = exp(poly(1/epsilon)). The key foundations of our algorithm are: (1) a simple yet powerful structural theorem which states that the union of a sequence of sparse length-constrained cuts is itself sparse and (2) new algorithms for efficiently computing sparse length-constrained flows.

关键词： expander decompositions graph algorithms length-constrained expander decompositions linear time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：