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

Cyclic Action graphs for goal recognition problems with inaccurately initialised fluents

KNOWLEDGE AND INFORMATION SYSTEMS 2024年第2期66卷 1257-1300页

作者： Harman, Helen Simoens, Pieter Univ Ghent Imec Dept Informat Technol IDLab Technol Pk 126 B-9052 Ghent Belgium Univ Lincoln Sch Comp Sci Lincoln Ctr Autonomous Syst L CAS Lincoln LN6 7TS England

Goal recognisers attempt to infer an agent's intentions from a sequence of observed actions. This is an important component of intelligent systems that aim to assist or thwart actors;however, there are many challenges to overcome. For example, the initial state of the environment could be partially unknown, and agents can act suboptimally and observations could be missing. Approaches that adapt classical planning techniques to goal recognition have previously been proposed, but, generally, they assume the initial world state is accurately defined. In this paper, a state is inaccurate if any fluent's value is unknown or incorrect. Our aim is to develop a goal recognition approach that is as accurate as the current state-of-the-art algorithms and whose accuracy does not deteriorate when the initial state is inaccurately defined. To cope with this complication, we propose solving goal recognition problems by means of an Action graph. An Action graph models the dependencies, i.e. order constraints, between all actions rather than just actions within a plan. Leaf nodes correspond to actions and are connected to their dependencies via operator nodes. After generating an Action graph, the graph's nodes are labelled with their distance from each hypothesis goal. This distance is based on the number and type of nodes traversed to reach the node in question from an action node that results in the goal state being reached. For each observation, the goal probabilities are then updated based on either the distance the observed action's node is from each goal or the change in distance. Our experimental results, for 15 different domains, demonstrate that our approach is robust to inaccuracies within the defined initial state.

关键词： Goal recognition graph algorithm Cyclic graph Inferring intent Context aware

来源：评论

学校读者我要写书评

暂无评论

Strong minimum energy -hop rooted topology for hierarchical wireless sensor networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第4期30卷 1077-1094页

作者： Panda, B. S. Shetty, D. Pushparaj Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraint that the resulting topology containing only bidirectional links is strongly connected. This problem is known to be NP-hard. However, most of the wireless sensor networks are hierarchical in nature, where shorter path lengths are preferred for communication between any two nodes. Given a set of sensors and a specified sensor, say , the strong minimum energy -hop rooted topology problem (h-SMERT) is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraints that the resulting topology containing only bidirectional links is strongly connected and the length of the path from to any other node is at most . We prove that the h-SMERT problem is NP-hard. We also prove that h-SMERT problem is APX-hard. We then show that h-SMERT problem is not approximable within a factor of 1/2 (1 - epsilon) unless NP subset of D T I M E (n(log log n)) On the positive side, we propose a -2(1 + ln n)-approximation algorithm for the h-SMERT problem. We also study two special cases of the h-SMERT problem, namely, the -rest-h-SMERT problem and the -int-h-SMERT problem. We propose a -approximation algorithm for the -rest-h-SMERT problem. The -int-h-SMERT problem is NP-hard for arbitrary . However, for fixed constant , we propose a -approximation algorithm for the -int-h-SMERT problem and obtain a polynomial time optimal algorithm for the -int-h-SMERT problem for k = 2.

关键词： Wireless sensor network Topology control problem Transmission power assignment graph algorithm NP-hard APX-hard Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

DETERMINING CONNECTED COMPONENTS IN LINEAR TIME BY A LINEAR NUMBER OF PROCESSORS

引用

INFORMATION PROCESSING LETTERS 1987年第6期25卷 401-406页

作者： PEPER, F Faculty of Mathematics and Informatics Delft University of Technology P.O. Box 356 2600 AJ Delft The Netherlands

Parallel algorithms for the problem of finding the connected components of a simple undirected graph are examined. These algorithms can be divided into 3 classes: 1. those that generally require a shared memory single instruction streams, multiple data streams (SIMD) model permitting read conflicts on the same memory location, 2. parallelizations of the algorithms operating on matrices, generally using SIMD processors with local memory connected by a regular network, and 3. those that use processors arranged in a binary tree. A lighthouse algorithm is described that has no loss in efficiency and can be used on a shared memory SIMD model. Read conflicts are permitted on the model, but simultaneous write operations or simultaneous write and read operations are not. In the lighthouse algorithm, each processor cyclically reads all of its neighbors' labels and compares them with its own label. The analysis indicates that the lighthouse algorithm efficiently determines the connected components in a graph.

关键词： Parallel processing graph algorithm transitive closure connected component graph theory

来源：评论

学校读者我要写书评

暂无评论

Partitioning vertices into in- and out-dominating sets in digraphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 285卷 43-54页

作者： Nakamura, Kosuke Araki, Toru Gunma Univ Div Elect & Informat Kiryu Gunma 3768515 Japan

For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consider the problem of determining whether there is a partition of the vertex set into in- and out-dominating sets of the digraph. In this paper, we obtain the following results: (1) The decision problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a polynomial time algorithm for deciding the existence of such partition. (C) 2020 Elsevier B.V. All rights reserved.

关键词： graph algorithm Domination Digraph In-domination Out-domination Domatic partition

来源：评论

学校读者我要写书评

暂无评论

Source location problem with flow requirements in directed networks

引用

OPTIMIZATION METHODS & SOFTWARE 2003年第4期18卷 427-435页

作者： Ito, H Makino, K Arata, K Honami, S Itatsu, Y Fujishige, S Osaka Univ Grad Sch Engn Sci Div Syst Sci Osaka Japan Kyoto Univ Grad Sch Math Dept Commun & Comp Engn Kyoto Japan Matsushita Commun Ind Co Ltd Yokohama Kanagawa Japan Kyoto Univ Math Sci Res Inst Kyoto Japan

Given a directed graph G = (V, A) with a capacity function c : A --> R+, two demand functions d(-), d(+) : V --> R+, and a cost function w : V --> R+, we consider the problem of computing a minimum-cost set S subset of or equal to V such that, for each vertex v is an element of V - S, the arc-connectivity from S to v is at least d(-)(v) and the arc-connectivity from v to S is at least d(+)(v). We present a polynomial time algorithm for the problem where d(-) and d(+) are uniformly fixed and w is uniform. Furthermore, we show that the problem is NP-hard, even if either the cost function or the demand function is uniform.

关键词： graph algorithm arc-connectivity location problem network flow deficient set tree hypergraph

来源：评论

学校读者我要写书评

暂无评论

A Linear Time algorithm for L(2,1)-Labeling of Trees

引用

algorithmICA 2013年第3期66卷 654-681页

作者： Hasunuma, Toru Ishii, Toshimasa Ono, Hirotaka Uno, Yushi Univ Tokushima Dept Math & Nat Sci Tokushima 7708502 Japan Hokkaido Univ Grad Sch Econ Div Modern Econ & Business Adm Sapporo Hokkaido 0600809 Japan Kyushu Univ Dept Econ Engn Fukuoka 8128581 Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|a parts per thousand yen2 if x and y are adjacent and |f(x)-f(y)|a parts per thousand yen1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)->{0,aEuro broken vertical bar,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Delta (4.5) n) for more than a decade, and an O(min{n (1.75),Delta (1.5) n})-time algorithm has appeared recently, where Delta and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.

关键词： Frequency/channel assignment graph algorithm L(2,1)-Labeling Vertex coloring

来源：评论

学校读者我要写书评

暂无评论

Swapping labeled tokens on graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年 586卷 81-94页

作者： Yamanaka, Katsuhisa Demaine, Erik D. Ito, Takehiro Kawahara, Jun Kiyomi, Masashi Okamoto, Yoshio Saitoh, Toshiki Suzuki, Akira Uchizawa, Kei Uno, Takeaki Iwate Univ Dept Elect Engn & Comp Sci Morioka Iwate 0208551 Japan MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma Nara 6300192 Japan Yokohama City Univ Int Coll Arts & Sci Kanazawa Ku Yokohama Kanagawa 2360027 Japan Univ Electrocommun Dept Commun Engn & Informat Chofu Tokyo 1828585 Japan Kobe Univ Grad Sch Engn Nada Ku Kobe Hyogo 6578501 Japan Yamagata Univ Grad Sch Sci & Engn Yonezawa Yamagata 9928510 Japan Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan

Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n(2)) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2 alpha-approximation algorithm for graphs whose tree a-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Approximation Complete bipartite graph graph algorithm Sorting network Tree

来源：评论

学校读者我要写书评

暂无评论

SIMPLE LINEAR-TIME algorithmS TO TEST CHORDALITY OF graphS, TEST ACYCLICITY OF HYPERgraphS, AND SELECTIVELY REDUCE ACYCLIC HYPERgraphS

引用

SIAM JOURNAL ON COMPUTING 1984年第3期13卷 566-579页

作者： TARJAN, RE YANNAKAKIS, M Bell Lab Murray Hill NJ USA Bell Lab Murray Hill NJ USA

Chordal graphs arise naturally in the study of Gaussian elimination on sparse symmetric matrices; acyclic hypergraphs arise in the study of relational data bases. Rose, Tarjan and Lueker [SIAM J. Comput., 5 (1976), pp. 266–283] have given a linear-time algorithm to test whether a graph is chordal, which Yannakakis has modified to test whether a hypergraph is acyclic. Here we develop a simplified linear-time test for graph chordality and hypergraph acyclicity. The test uses a new kind of graph (and hypergraph) search, which we call maximum cardinality search A variant of the method gives a way to selectively reduce acyclic hypergraphs, which is needed for evaluating queries in acyclic relational data bases.

关键词： graph algorithm acyclic data base scheme sparse Gaussian elimination graph search hypergraph

来源：评论

学校读者我要写书评

暂无评论

Disk embeddings of planar graphs

引用

algorithmICA 2004年第4期38卷 539-576页

作者： Chen, ZZ He, X Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA

Given a planar graph G = (V, E) and a rooted forest F = (V-F, A(F),) with leaf set V, we wish to decide whether G has a plane embedding 9 satisfying the following condition: There are \V-F\ - \V\ pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of 17 such that for every nonleaf vertex f of F, the interior of the curve T-f corresponding to f contains all the leaf descendants of f in T but contains no other leaves of F. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex f in F induces a connected subgraph of G.

关键词： graph algorithm planar graph planar embedding

来源：评论

学校读者我要写书评

暂无评论

Balanced vertex-orderings of graphs

引用

DISCRETE APPLIED MATHEMATICS 2005年第1期148卷 27-48页

作者： Biedl, T Chan, T Ganjali, Y Hajiaghayi, MT Wood, DR Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Stanford Univ Dept Elect Engn Stanford CA 94305 USA MIT Comp Sci Lab Cambridge MA 02139 USA Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

In this paper we consider the problem of determining a balanced ordering of the vertices of a graph;, that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This problem, which has applications in graph drawing for example, is shown to be hard, and remains NP-hard for bipartite simple graphs with maximum degree six. We then describe and analyze a number of methods for determining a balanced vertex-ordering, obtaining optimal orderings for directed acyclic graphs, trees, and graphs with maximum degree three. For undirected graphs, we obtain a 13 / 8- approximation algorithm. Finally we consider the problem of determining a balanced vertex-ordering of a bipartite graph with a fixed ordering of one bipartition. When only the imbalances of the fixed vertices count, this problem is shown to be NP-hard. On the other hand, we describe an optimal linear time algorithm when the final imbalances of all vertices count. We obtain a linear time algorithm to compute an optimal vertex-ordering of a bipartite graph with one bipartition of constant size. (c) 2004, Elsevier B.V. All rights reserved.

关键词： graph algorithm graph drawing vertex-ordering balanced

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：