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

An algorithm for shortest paths in bipartite digraphs with concave weight matrices and its applications

SIAM JOURNAL ON COMPUTING 1999年第1期29卷 65-80页

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

The traveling salesman problem on an n-point convex polygon and the minimum latency tour problem for n points on a straight line are two basic problems in graph theory and have been studied in the past. Previously, it was known that both problems can be solved in O(n(2)) time. However, whether they can be solved in o(n(2)) time was left open by Marcotte and Suri [SIAM J. Comput., 20 (1991), pp. 405-422] and Afrati et al. [Informatique Theorique Appl., 20 (1986), pp. 79-87], respectively. In this paper we show that both problems can be solved in O(n log n) time by reducing them to the following problem: Given an edge-weighted complete bipartite digraph G = (X, Y, E) with X = {x(0),..., x(n)} and Y = {y(0),..., y(m)}, we wish to find the shortest path from x(0) to x(n) in G. This new problem requires Omega(nm) time to solve in general, but we show that it can be solved in O(n + m log n) time if the weight matrices A and B of G are both concave, where for 0 less than or equal to i less than or equal to n and 0 less than or equal to j less than or equal to m, A[i, j] and B[j, i] are the weights of the edges (x(i), y(j)) and (y(j), x(i)) in G, respectively. As demonstrated in this paper, the new problem is a powerful tool and we believe that it can be used to solve more problems.

关键词： graph algorithm shortest path traveling salesman problem minimum latency tour problem concave matrix

来源：评论

学校读者我要写书评

暂无评论

Centrality measures-based algorithm to visualize a maximal common induced subgraph in large communication networks

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2016年第1期46卷 213-239页

作者： Nirmala, Parisutham Sulochana, Lekshmi Ramasubramony Rethnasamy, Nadarajan PSG Coll Technol Dept Appl Math & Computat Sci Coimbatore 641004 Tamil Nadu India

Communication networks are ubiquitous, increasingly complex, and dynamic. Predicting and visualizing common patterns in such a huge graph data of communication network is an essential task to understand active patterns evolved in the network. In this work, the problem is to find an active pattern in a communication network which is modeled as detection of a maximal common induced subgraph (CIS). The state of the communication network is captured as a time series of graphs which has periodic snapshots of logical communications within the network. A new centrality measure is proposed to assess the variation in successive graphs and to identify the behavior of each node in the time series graph. It extents help in the process of selecting a suitable candidate vertex for maximality in each step of the proposed algorithm. This paper is a pioneer attempt in using centrality measures to detect a maximal CIS of the huge graph database, which gives promising effect in the resultant graph in terms of large number of vertices. The algorithm has polynomial time complexity, and the efficiency of the algorithm is demonstrated by a series of experiments with synthetic graph datasets of different orders. The performance of real-time datasets further ensured the competence of the proposed algorithm.

关键词： Communication networks Similarity pattern graph mining Substructure mining Information extraction graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for weak Roman domination

引用

DISCRETE APPLIED MATHEMATICS 2018年 248卷 79-92页

作者： Chapelle, Mathieu Cochefert, Manfred Couturier, Jean-Francois Kratsch, Dieter Letourneur, Romain Liedloff, Mathieu Perez, Anthony IFTS CReSTIC Pole Haute Technol F-08000 Charleville Mezieres France Univ Lorraine Lab Informat Theor & Appl F-57045 Metz 01 France Univ Orleans INSA Ctr Val Loire LIFO EA 4022 FR-45067 Orleans France

We consider the WEAK ROMAN DOMINATION problem. Given an undirected graph G = (V, E), the aim is to find a weak Roman domination function (wrd-function for short) of minimum cost, i.e. a function f : V -> {0, 1, 2} such that every vertex v is an element of V is defended (i.e. there exists a neighbor u of v, possibly u = v, such that f (u) >= 1) and for every vertex v is an element of V with f (v) = 0 there exists a neighbor u of v such that f (u) >= 1 and the function f(u -> v) defined by f(u -> v)(v) = 1, f(u -> v)(u) = f (u) - 1 and f(u -> v)(x) = f(x) otherwise does not contain any undefended vertex. The cost of a wrd-function f is defined by cost(f) = Sigma(v is an element of V)f(v). The trivial enumeration algorithm runs in time O*(3(n)) and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in O*(2(n)) time needing exponential space, and then describe an O*(2.2279(n)) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the RED-BLUE DOMINATING SET problem. Moreover we show that the problem can be solved in linear-time on interval graphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Exact algorithm graph algorithm Roman domination Interval graphs

来源：评论

学校读者我要写书评

暂无评论

Route planning with turn restrictions: A computational experiment

引用

OPERATIONS RESEARCH LETTERS 2012年第5期40卷 342-348页

作者： Vanhove, Stephanie Fack, Veerle Univ Ghent Dept Appl Math & Comp Sci B-9000 Ghent Belgium

Real-world road networks often contain turn penalties or forbidden turns. Standard shortest path algorithms do not take these into account. Several ways of dealing with such turn restrictions have been proposed. It has remained unclear which method is most suitable, even though efficiency is very important in route planning. We present a computational experiment comparing these methods. We conclude with a guideline for choosing the right algorithm in a real-world application. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Routing Turn cost Turn prohibition graph algorithm Shortest path

来源：评论

学校读者我要写书评

暂无评论

Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time

引用

ACM TRANSACTIONS ON algorithmS 2024年第1期20卷 1-26页

作者： Cairo, Massimo Rizzi, Romeo Tomescu, Alexandru I. Zirondelli, Elia C. Univ Helsinki Dept Comp Sci POB 68 FI-00014 Helsinki Finland Univ Verona Dept Comp Sci CaVignal 2Str Grazie 15 I-37134 Verona Italy Univ Trento Dept Math Via Sommar 14 I-38123 Povo Italy

Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major theoretical advances. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. While such paths constitute only partial assemblies, they are likely to be correct. More precisely, if one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. Until recently, it was open what are all the safe walks of an assembly graph. Tomescu and Medvedev (RECOMB 2016) characterized all such safe walks (omnitigs), thus giving the first safe and complete genome assembly algorithm. Even though maximal omnitig finding was later improved to quadratic time by Cairo et al. (ACM Trans. algorithms 2019), it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We answer this question affirmatively, by describing a surprising O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with T(mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig. This has two consequences: (1) A linear-time output-sensitive algorithm enumerating all maximal omnitigs. (2) A compact O(m) representation of all maximal omnitigs, which allows, e.g., for O(m)-time computation of various statistics on them. Our results close a long-standing theoretical question inspired by practical genome assemblers, originating with the use of unitigs in 199

关键词： graph algorithm strong connectivity reachability under failures

来源：评论

学校读者我要写书评

暂无评论

Leveraging health social networking communities in translational research

引用

JOURNAL OF BIOMEDICAL INFORMATICS 2011年第4期44卷 536-544页

作者： Webster, Yue W. Dow, Ernst R. Koehler, Jacob Gudivada, Ranga C. Palakal, Mathew J. Eli Lilly & Co Lilly Corp Ctr Discovery Informat Indianapolis IN 46285 USA Indiana Univ Purdue Univ Sch Informat Indianapolis IN USA

Health social networking communities are emerging resources for translational research. We have designed and implemented a framework called HyGen, which combines Semantic Web technologies, graph algorithms and user profiling to discover and prioritize novel associations across disciplines. This manuscript focuses on the key strategies developed to overcome the challenges in handling patient-generated content in Health social networking communities. Heuristic and quantitative evaluations were carried out in colorectal cancer. The results demonstrate the potential of our approach to bridge silos and to identify hidden links among clinical observations, drugs, genes and diseases. In Amyotrophic Lateral Sclerosis case studies, HyGen has identified 15 of the 20 published disease genes. Additionally, HyGen has highlighted new candidates for future investigations, as well as a scientifically meaningful connection between riluzole and alcohol abuse. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Translational research Health social networking Semantic Web graph algorithm

来源：评论

学校读者我要写书评

暂无评论

The hidden algorithm of Ore's theorem on Hamiltonian cycles

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1997年第11期34卷 113-119页

作者： Palmer, EM Department of Mathematics Michigan State University East Lansing MI 48824 USA palmer@math.msu.edu

In 1960, Ore found a simple sufficient condition for a graph to have a Hamiltonian cycle. We expose a heuristic algorithm, hidden in Ore's proof, which can be very effective in actually finding such a cycle. This ... 详细信息

关键词： graph algorithm Hamiltonian probability

来源：评论

学校读者我要写书评

暂无评论

Hardness results and approximation algorithm for total liar's domination in graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2014年第4期27卷 643-662页

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

In this paper, we initiate the study of total liar's domination of a graph. A subset LaS dagger V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all vaV, |N (G) (v)a (c) L|a parts per thousand yen2 and (ii) for every pair u,vaV of distinct vertices, |(N (G) (u)a(a)N (G) (v))a (c) L|a parts per thousand yen3. The total liar's domination number of a graph G is the cardinality of a minimum total liar's dominating set of G and is denoted by gamma (TLR) (G). The Minimum Total Liar's Domination Problem is to find a total liar's dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar's Domination Decision Problem is to check whether G has a total liar's dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar's dominating set in a graph. We show that the Total Liar's Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(ln Delta(G)+1)-approximation algorithm for the Minimum Total Liar's Domination Problem, where Delta(G) is the maximum degree of the input graph G. We show that Minimum Total Liar's Domination Problem cannot be approximated within a factor of for any I mu > 0, unless NPaS dagger DTIME(|V|(loglog|V|)). Finally, we show that Minimum Total Liar's Domination Problem is APX-complete for graphs with bounded degree 4.

关键词： Domination Liar's domination Chordal graph graph algorithm Approximation algorithm NP-completeness APX-completeness

来源：评论

学校读者我要写书评

暂无评论

algorithms solving the Matching Cut problem

引用

THEORETICAL COMPUTER SCIENCE 2016年第Part2期609卷 328-335页

作者： Kratsch, Dieter Van Bang Le Univ Lorraine Lab Informat Theor & Appl F-57045 Metz 01 France Univ Rostock Inst Informat D-18055 Rostock Germany

In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete. This paper provides a first branching algorithm solving MATCHING Cur in time O*(2(n/2)) = O*(1.4143(n)) for an n-vertex input graph, and shows that MATCHING CUT parameterized by the vertex cover number tau(G) can be solved by a single-exponential algorithm in time 2 tau((G)) O(n(2)). Moreover, the paper also gives a polynomially solvable case for MATCHING Cur which covers previous known results on graphs of maximum degree three, line graphs, and claw-free graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Matching cut graph algorithm

来源：评论

学校读者我要写书评

暂无评论

AN O(N LOG2 N) algorithm FOR MAXIMUM FLOW IN UNDIRECTED PLANAR NETWORKS

引用

SIAM JOURNAL ON COMPUTING 1985年第3期14卷 612-624页

作者： HASSIN, R JOHNSON, DB PENN STATE UNIV DEPT COMP SCIUNIVERSITY PKPA 16802

A new algorithm is given to find a maximum flow in an undirected planar flow network in $O(n\log ^2 n)$ time, which is faster than the best method previously known by a factor of $\sqrt n /\log n$. The algorithm constructs a transformation of the dual of the given flow network in which differences between shortest distances are equal, under suitable edge correspondences, to edge flows in the given network. The transformation depends on the value of a maximum flow. The algorithm then solves the shortest distances problem efficiently by exploiting certain structural properties of the transformed dual, as well as using a set of cuts constructible in $O(n\log ^2 n)$ time by a known method which is also used to find the requisite flow value. The main result can be further improved by a factor of $\log n/\log^* n$ if a recently developed shortest path algorithm for planar networks is used in place of Dijkstra’s algorithm in each step where shortest paths are computed.

关键词： flow maximum flow planar network duality graph algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：