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

4th Conference on Computational Models of Argument (COMMA)

作者： Nofal, Samer Dunne, Paul Atkinson, Katie Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

ISBN: (纸本)9781614991113;9781614991106

From theoretical computational perspectives, decision problems in Dung's abstract argumentation frameworks (AFs) are either polynomial solvable or intractable. To investigate practical efficiency, theoretical evaluation of applied algorithms does not necessarily reveal performance dissimilarities. Although experimental analysis of algorithms is a well-established alternative exploited in other domains, such methodology is given a little attention in the context of AFs. The main purpose of this paper is to give an example of how such experiments can be conducted to get meaningful conclusions about algorithms' behavior in situations where theoretical analysis might be of little help. To this end, we pick an extended model of AFs as a case study to empirically examine the efficiency of algorithms related to the acceptability of arguments.

关键词： experimental algorithms credulous acceptance skeptical acceptance

来源：评论

学校读者我要写书评

暂无评论

Temporal betweenness centrality on shortest walks variants

引用

APPLIED NETWORK SCIENCE 2025年第1期10卷 1-25页

作者： Naima, Mehdi Sorbonne Univ LIP6 CNRS F-75005 Paris France

Betweenness centrality has been extensively studied since its introduction in 1977 as a measure of node importance in graphs. This measure has found use in various applications and has been extended to temporal graphs with time-labeled edges. Recent research by Bu ss et al. and Rymar et al. has shown that it is possible to compute the shortest walks betweenness centrality of all nodes in a temporal graph in On3T2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n<^>3\,T<^>2\right)$$\end{document} and On2mT2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n<^>2\,m\,T<^>2\right)$$\end{document} time, respectively, where T is the maximum time, m is the number of temporal edges, and n is the number of nodes. These approaches considered walks that do not take into account contributions from intermediate temporal nodes. In this paper, we study the temporal betweenness centrality on classical walks that we call passive, as well as on a variant that we call active walks, which takes into account contributions from all temporal nodes. We present an improved analysis of the running time of the classical algorithm for computing betweenness centrality of all nodes, reducing the time complexity to OnmT+n2T\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( n\,m\,T+ n<^>2\,T\right)$$\end{document}. Furthermore, for active walks, we show that the betweenness centrality can be computed in OnmT+n2T2\documentclass[12pt]{minimal} \u

关键词： Graph algorithms experimental algorithms Betweenness centrality Temporal graphs Shortest paths Time centrality Restless walks

来源：评论

学校读者我要写书评

暂无评论

Sampling strategies for mining in data-scarce domains

引用

COMPUTING IN SCIENCE & ENGINEERING 2002年第4期4卷 31-43页

作者： Ramakrishnan, N Bailey-Kellogg, C Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

A novel framework leverages physical properties for mining in data-scarce domains. It interleaves bottom-up data mining with top-down data collection, leading to effective and explainable sampling strategies.

关键词： Data Mining Sampling Experiment Design Qualitative Reasoning experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Engineering Quicksort

引用

COMPUTER LANGUAGES 1996年第1期22卷 39-47页

作者： Sarwar, SM Sarwar, SA Jaragh, MHA Brandeburg, J NEW YORK INST TECHNOL ACAD COMP LABSOLD WESTBURYNY 11568 KUWAIT UNIV FAC ENGN & PETRDEPT ELECT & COMP ENGNSAFAT 13060KUWAIT

This paper describes the results of a large empirical study to measure the run-time behavior of Quicksort by using various methods of computing the pivot element for medium to large size randomly generated integer data. The results of our study contradict the common notion that Quicksort gives best performance if median of three scheme is used to compute the pivot element and array partitions having <10 elements are sorted by using insertion sort. It was found that Quicksort performs best when median of three scheme is used to decide the pivot element and arrays with <4 elements are hand sorted. Our method gives an average speedup of >9% when compared to the method with a cutoff of 10 and sub-arrays with <10 elements insertion sorted for 1000 less than or equal to N less than or equal to 1.5 x 10(6). Our study shows that advanced hardware features allow for implementation of very fast codes for sorting small arrays, and using such codes instead of insertion sort can lead to substantial improvements for Quicksort, as conjectured by Sedgewick many years ago. Copyright (C) 1996 Elsevier Science Ltd

关键词： experimental algorithms sorting algorithms Quicksort

来源：评论

学校读者我要写书评

暂无评论

Distance-preserving approximations of polygonal paths

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第3期36卷 183-196页

作者： Gudmundsson, Joachim Narasimhan, Giri Smid, Michiel Florida Int Univ Sch Comp Sci Miami FL 33199 USA Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

Given a polygonal path P with vertices p(1), p(2),..., p(n) is an element of R-d and a real number t >= 1, a path Q = (p(i1), p(i2),...,P-ik) is a t-distance-preserving approximation of P if 1 = i(1) < i(2) < ... < i(k) = n and each straight-line edge (p(ij), p(ij+1)) of Q approximates the distance between pi(j) and pi(j+1) along the path P within a factor of t. We present exact and approximation algorithms that compute Such a path Q that minimizes k (when given t) or t (when given k). We also present some experimental results. (c) 2006 Elsevier B.V. All rights reserved.

关键词： path simplification t-spanners well-separated pair decomposition experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling periodic messages on a shared link without buffering

引用

JOURNAL OF SCHEDULING 2024年第5期27卷 461-484页

作者： Guiraud, Mael Strozecki, Yann CESI Nanterre LINEACT BP 60293 Blvd Seine F-92006 Nanterre France Univ Versailles St Quentin DAVID Lab 45 Ave Etats Unis F-78000 Versailles France

Cloud RAN, a novel architecture for modern mobile networks, relocates processing units from antenna to distant data centers. This shift introduces the challenge of ensuring low latency for the periodic messages exchanged between antennas and their respective processing units. In this study, we tackle the problem of devising an efficient periodic message assignment scheme under the constraints of fixed message size and period without contention nor buffering. We address this problem by modeling it on a common network topology, wherein contention arises from a single shared link servicing multiple antennas. While reminiscent of coupled task scheduling, the introduction of periodicity adds a unique dimension to the problem. We study how the problem behaves with regard to the load of the shared link, and we focus on proving that, for load as high as possible, a solution always exists and it can be found in polynomial time. The main contributions of this article are two polynomial time algorithms, which find a solution for messages of any size and load at most 2/5 or for messages of size one and load at most phi-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi - 1$$\end{document}, the golden ratio conjugate. We also prove that a randomized greedy algorithm finds a solution on almost all instances with high probability, shedding light on the effectiveness of greedy algorithms in practical applications.

关键词： Periodic scheduling Greedy algorithm Randomized algorithm experimental algorithms C-RAN

来源：评论

学校读者我要写书评

暂无评论

A weak approach to suffix automata simulation for exact and approximate string matching

引用

THEORETICAL COMPUTER SCIENCE 2022年 933卷 88-103页

作者： Faro, Simone Scafiti, Stefano Univ Catania Dept Math & Comp Sci Viale A Doria 6 I-95125 Catania Italy

String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However, automata have always played a very important role in the design of efficient string matching algorithms. In this paper we present the Range Automaton, a weak yet efficient variant of the non-deterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving a multitude of text-searching problems. We will firstly develop our approach in the case of exact string matching and present an efficient algorithm, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Later, we will show how the Range Automaton can be adapted in an effective way also to non-standard string matching problems such as swap matching and multiple string matching. experimental results suggest that our approach is flexible and effective for all three search problems addressed, especially in the case of long patterns. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Exact string matching Swap matching Text processing Automata experimental algorithms Design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

The Exact Online String Matching Problem: A Review of the Most Recent Results

引用

ACM COMPUTING SURVEYS 2013年第2期45卷 1–42页

作者： Faro, Simone Lecroq, Thierry Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France

This article addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. In this article we review the string matching algorithms presented in the last decade and present experimental results in order to bring order among the dozens of articles published in this area.

关键词： algorithms Design Experimentation String matching experimental algorithms text processing automaton

来源：评论

学校读者我要写书评

暂无评论

On comparing algorithms for the maximum clique problem

引用

DISCRETE APPLIED MATHEMATICS 2018年 247卷 1-13页

作者： Zuge, Alexandre Prusch Carmo, Renato UFPR Campus Avanado Jandaia do Sul BR-86900000 Jandaia Do Sul PR Brazil Univ Fed Parana Ctr Politecn UFPR Dept Informat POB 19081 BR-81531990 Curitiba Parana Brazil

Several algorithms for the exact solution of the maximum clique problem are available in the literature. Some have been proposed with the aim of bounding the worst case complexity of the problem, while others focus on practical performance as evaluated experimentally. These two groups of works are somewhat independent, in the sense that little experimental investigation is available in the former group, and little theoretical analysis exists for the latter. Moreover, the experimental results seem to be much better than could be expected from the theoretical results. We show that a broad class of branch and bound algorithms for the maximum clique problem display sub-exponential average running time behavior, and also show how this helps to explain the apparent discrepancy between the theoretical and experimental results. We also propose a more structured methodology for the experimental analysis of algorithms for the maximum clique problem, which takes into account the peculiarities of cliques in random graphs, bringing the theoretical and experimental approaches closer together in the search for better algorithms. As a proof of concept, we apply the proposed methodology to thirteen algorithms from the literature. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Maximum clique experimental algorithms Random graphs Branch and bound

来源：评论

学校读者我要写书评

暂无评论

Hybrid string matching algorithm with a pivot

引用

JOURNAL OF INFORMATION SCIENCE 2015年第1期41卷 82-88页

作者： Al-Ssulami, Abdulrakeeb M. King Saud Univ Riyadh 11543 Saudi Arabia

Pattern matching is important in text processing, molecular biology, operating systems and web search engines. Many algorithms have been developed to search for a specific pattern in a text, but the need for an efficient algorithm is an outstanding issue. In this paper, we present a simple and practical string matching algorithm. The proposed algorithm is a hybrid that combines our modification of Horspool's algorithm with two observations on string matching. The algorithm scans the text from left to right and matches the pattern from right to left. experimental results on natural language texts, genomes and human proteins demonstrate that the new algorithm is competitive with practical algorithms.

关键词： Design of algorithms experimental algorithms online string searching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：