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

arXiv 2023年

作者： Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. LIRMM Univ Montpellier CNRS Montpellier France

We establish a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering ≤ on graphs. At the center of this framework lies the concept of a ≤-parametric graph: a non ≤-decreasing sequence G = 〈Gt〉t∈N of graphs indexed by non-negative integers. Parametric graphs allow us to define combinatorial objects that capture the approximate behaviour of graph parameters. A finite set G of ≤-parametric graphs is a ≤-universal obstruction for a parameter p if there exists a function f : N → N such that, for every k ∈ N and every graph G, 1) if p(G) ≤ k, then for every G ∈ G, Gf(k) G, and 2) if for every G ∈ G, Gk G, then p(G) ≤ f(k). To solidify our point of view, we identify sufficient order-theoretic conditions that guarantee the existence of universal obstructions and in this case we examine algorithmic implications on the existence of fixed-parameter tractable algorithms. Our parametric framework has further implications related to finite obstruction characterizations of properties of graph classes. A ≤-class property is defined as any set of ≤-closed graph classes that is closed under set inclusion. By combining our parametric framework with established results from order theory, we derive a precise order-theoretic characterization that ensures ≤-class properties can be described in terms of the exclusion of a finite set of ≤-parametric *** Codes 06A07, 05C83, 05C85 © 2023, CC BY.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Near-gathering of energy-constrained mobile agents

引用

THEORETICAL COMPUTER SCIENCE 2021年 849卷 35-46页

作者： Baertschi, Andreas Bampas, Evangelos Chalopin, Jeremie Das, Shantanu Karousatou, Christina Mihalak, Maths Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA Paris Saclay Univ St Aubin France CNRS LRI Paris France Aix Marseille Univ CNRS Marseille France Univ Toulon & Var LIS Toulon France Tech Univ Darmstadt Dept Math Darmstadt Germany Maastricht Univ Dept Data Sci & Knowledge Engn Maastricht Netherlands

We study the task of gathering k energy-constrained mobile agents in an undirected edge-weighted graph. Each agent is initially placed on an arbitrary node and has a limited amount of energy, which constrains the distance it can move. Since this may render gathering at a single point impossible, we study three variants of near-gathering: The goal is to move the agents into a configuration that minimizes either (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents. We prove that (i) is polynomial-time solvable, (ii) has a polynomial-time 2-approximation with a matching NP-hardness lower bound, while (iii) admits a polynomial-time 2(1 - 1/k)-approximation, but no FPTAS, unless P = NP. We extend some of our results to additive approximation. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Mobile agents Power-aware robots Limited battery Gathering graph algorithms Approximation Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient and Accurate PageRank Approximation on Large graphs

引用

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

作者： Siyue Wu Dingming Wu Junyi Quan Tsz Nam Chan Kezhong Lu Shenzhen University Shenzhen China Shenzhen University Shenzhen HK

PageRank is a commonly used measurement in a wide range of applications, including search engines, recommendation systems, and social networks. However, this measurement suffers from huge computational overhead, which cannot be scaled to large graphs. Although many approximate algorithms have been proposed for computing PageRank values, these algorithms are either (i) not efficient or (ii) not accurate. Worse still, some of them cannot provide estimated PageRank values for all the vertices. In this paper, we first propose the CUR-Trans algorithm, which can reduce the time complexity for computing PageRank values and has lower error bound than existing matrix approximation-based PageRank algorithms. Then, we develop the T 2-Approx algorithm to further reduce the time complexity for computing this measurement. Experiment results on three large-scale graphs show that both the CUR-Trans algorithm and the T 2-Approx algorithm achieve the lowest response time for computing PageRank values with the best accuracy (for the CUR-Trans algorithm) or the competitive accuracy (for the T 2-Approx algorithm). Besides, the two proposed algorithms are able to provide estimated PageRank values for all the vertices.

关键词： approximation algorithms graph algorithms pagerank

来源：评论

学校读者我要写书评

暂无评论

algorithms for gerrymandering over graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 868卷 30-45页

作者： Ito, Takehiro Kamiyama, Naoyuki Kobayashi, Yusuke Okamoto, Yoshio Tohoku Univ Sendai Miyagi Japan Kyushu Univ Fukuoka Japan JST PRESTO Kawaguchi Saitama Japan Kyoto Univ Kyoto Japan Univ Electrocommun Chofu Tokyo Japan

We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Gerrymandering Computational social choice graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Hyppo-X: A Scalable Exploratory Framework for Analyzing Complex Phenomics Data

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2021年第4期18卷 1535-1548页

作者： Kamruzzaman, Methun Kalyanaraman, Ananth Krishnamoorthy, Bala Hey, Stefan Schnable, Patrick S. Washington State Univ Sch Elect Engn & Comp Sci Pullman WA 99164 USA Washington State Univ Dept Math & Stat Vancouver WA 98686 USA Iowa State Univ Dept Agron Ames IA 50011 USA

Phenomics is an emerging branch of modern biology that uses high throughput phenotyping tools to capture multiple environmental and phenotypic traits, often at massive spatial and temporal scales. The resulting high dimensional data represent a treasure trove of information for providing an in-depth understanding of how multiple factors interact and contribute to the overall growth and behavior of different genotypes. However, computational tools that can parse through such complex data and aid in extracting plausible hypotheses are currently lacking. In this article, we present Hyppo-X, a new algorithmic approach to visually explore complex phenomics data and in the process characterize the role of environment on phenotypic traits. We model the problem as one of unsupervised structure discovery, and use emerging principles from algebraic topology and graph theory for discovering higher-order structures of complex phenomics data. We present an open source software which has interactive visualization capabilities to facilitate data navigation and hypothesis formulation. We test and evaluate Hyppo-X on two real-world plant (maize) data sets. Our results demonstrate the ability of our approach to delineate divergent subpopulation-level behavior. Notably, our approach shows how environmental factors could influence phenotypic behavior, and how that effect varies across different genotypes and different time scales. To the best of our knowledge, this effort provides one of the first approaches to systematically formalize the problem of hypothesis extraction for phenomics data. Considering the infancy of the phenomics field, tools that help users explore complex data and extract plausible hypotheses in a data-guided manner will be critical to future advancements in the use of such data.

关键词： Feature extraction Agriculture Data mining Topology Tools Data visualization Biology Computational phenomics topological data analysis graph algorithms hypothesis extraction visualization

来源：评论

学校读者我要写书评

暂无评论

A fast algorithm for source-wise round-trip spanners

引用

THEORETICAL COMPUTER SCIENCE 2021年 876卷 34-44页

作者： Zhu, Chun Jiang Han, Song Lam, Kam-Yiu Univ N Carolina Dept Comp Sci Greensboro NC 27412 USA Univ Connecticut Dept Comp Sci & Engn Storrs CT USA City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

In this paper, we study the problem of fast constructions of source-wise round-trip spanners in weighted directed graphs. For a source vertex set S subset of V in a graph G(V, E), an S-sourcewise round-trip spanner of G of stretch k is a subgraph H of G such that for every pair of vertices u, v is an element of S x V, their round-trip distance in H is at most k times of their round-trip distance in G. We show that for a graph G(V, E) with n vertices and m edges, an s-sized source vertex set S subset of V and an integer k >1, there exists an algorithm that in time O (ms(1/k) log(5) n) constructs an S-sourcewise round-trip spanner of stretch O(k log n) and O (ns(1/k) log(2) n) edges with high probability. Compared to the fast algorithms for constructing all-pairs round-trip spanners [26,12], our algorithm improves the running time and the number of edges in the spanner when k is super-constant. Compared with the existing algorithm for constructing source-wise round-trip spanners [36], our algorithm significantly improves their construction time c2(min{ms, n omega}) (where omega is an element of [2, 2.373) and 2.373 is the matrix multiplication exponent) to nearly linear O (ms1/k log5 n), at the expense of paying an extra O (log n) in the stretch. As an important building block of the algorithm, we develop a graph partitioning algorithm to partition G into clusters of bounded radius and prove that for every u, v is an element of S x V at small round-trip distance, the probability of separating them in different clusters is small. The algorithm takes the size of S as input and does not need the knowledge of S. With the algorithm and a reachability vertex size estimation algorithm, we show that the recursive algorithm for constructing standard round-trip spanners [26] can be adapted to the source-wise setting. We rigorously prove the correctness and computational complexity of the adapted algorithms. Finally, we show how to remove the dependence on the edge weight in the

关键词： graph spanners Round-trip spanners graph algorithms graph partitioning

来源：评论

学校读者我要写书评

暂无评论

An O*(2.619^k) algorithm for 4-PATH VERTEX COVER

引用

DISCRETE APPLIED MATHEMATICS 2021年 291卷 1-14页

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

In the 4-PATH VERTEX COVER problem, the input is an undirected graph G and an integer k. The goal is to decide whether there is a set S of vertices of size at most k such that every path with 4 vertices in G contains at least one vertex of S. In this paper we give a parameterized algorithm for 4-PATH VERTEX COVER whose time complexity is 2.619(k). n(O)(1), where n denotes the number of vertices of the input graph. (C) 2020 Elsevier B.V. All rights reserved.

关键词： graph algorithms Parameterized complexity Iterative compression Branching rules

来源：评论

学校读者我要写书评

暂无评论

A Scalable Buffer Queue Sizing Algorithm for Latency Insensitive Systems

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2021年第11期40卷 2386-2399页

作者： Maji, Supriyo Koh, Cheng-Kok Purdue Univ Dept Elect & Comp Engn W Lafayette IN 47907 USA Cadence Design Syst San Jose CA 95134 USA

Timing violations in high performance communication channels in system-on-chips (SoC) may occur in the late stages of the physical design process. To address that, latency insensitive systems (LISs) employ pipelining in the communication channels through the insertion of relay stations. Although the functionality of an LIS is robust with respect to the communication latencies, imbalances in relay station insertion may degrade the throughput of the system. While having a large number of buffer queues can eliminate such performance loss, the system may not have adequate area to accommodate these buffers. The problem of buffer queue sizing for maximizing throughput while meeting buffer area constraints has been solved using a mixed-integer linear program (MILP) formulation;however, such an approach is not scalable. In this work, we formulate the buffer queue sizing problem as a parameterized graph optimization problem where for every communication channel there is a parameterized edge with buffer counts as the edge weight. We then use a minimum cycle mean algorithm to determine from which edges buffers can be removed safely. Experimental results on large LISs suggest that the proposed approach is scalable. Moreover, quality of the solutions, in terms of the throughput and the size of buffer queues, is observed to be as good as that of the MILP-based approach.

关键词： Buffer queue sizing graph algorithms latency insensitive systems minimum balancing minimum cycle mean mixed integer linear programming throughput optimization timing optimization

来源：评论

学校读者我要写书评

暂无评论

Enhancing link prediction in dynamic networks using content aggregation

引用

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS 2021年第4期24卷 3055-3063页

作者： Bouakkaz, Mustapha Ouinten, Youcef Loudcher, Sabine Fournier-Viger, Philippe Univ Laghouat LIM Lab Laghouat Algeria Lyon2 Univ ERIC Lab Lyon France Harbin Inst Technol Shenzhen Peoples R China

For the last decade, social networking websites have boosted interaction among people through the use of digital communication such as chats, comments, discussion boards and exchange of documentation. This lead to mutual learning and sharing of all kind of information. This phenomenon has attracted many researchers and techniques aiming at discovering and prediction links between people have been developed. Most existing solutions are based on the similarity in the profiles using the declared personal information. We present in this paper an approach to discover and predict semantic links between members of a social network based on the content analysis. Our approach uses a textual aggregation function to aggregate keywords extracted from people's textual production. The result of this aggregation is then used to predict semantic links between the members of the network. Experiments were carried out using a real scientific corpus extracted from ReseachGate Web Site. The obtained results showed that our approach, compared to others, achieves better performances in terms of recall, precision, F-measure, complexity and runtime.

关键词： Link prediction Textual aggregation Social networks analysis graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The game of Cops and Eternal Robbers

引用

THEORETICAL COMPUTER SCIENCE 2021年 874卷 80-93页

作者： Bonato, Anthony Huggan, Melissa A. Marbach, Trent G. Inerney, Fionn Mc Ryerson Univ Toronto ON Canada Aix Marseille Univ CNRS Lab Informat & Syst Marseille France Univ Toulon & Var Fac Sci Luminy Marseille France

We introduce the game of Cops and Eternal Robbers played on graphs, where there are infinitely many robbers that appear sequentially over distinct plays of the game. A positive integer t is fixed, and the cops are required to capture the robber in at most t time-steps in each play. The associated optimization parameter is the eternal cop number, denoted by c(t)(infinity), which equals the eternal domination number in the case t = 1, and the cop number for sufficiently large t. We study the complexity of Cops and Eternal Robbers, and show that the game is NP-hard when t is a fixed constant and EXPTIME-complete for large values of t. We determine precise values of c(t)(infinity) for paths and cycles. The eternal cop number is studied for retracts, and this approach is applied to give bounds for trees, as well as for strong and Cartesian grids. (C) 2021 Published by Elsevier B.V.

关键词： Pursuit-evasion games Cops and Robbers graph algorithms Trees Retracts Grids

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：