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

A New Approach to graph Recognition and Applications to Distance-Hereditary graphs

Journal of Computer Science & Technology 2009年第3期24卷 517-533页

作者： Shin-ichi Nakano Ryuhei Uehara Takeaki Uno Department of Computer Science Faculty of EngineeringGunma UniversityGunma 376-8515Japan School of Information Science Japan Advanced Institute of Science and TechnologyIshikawa 923-1292Japan National Institute of Informatics Tokyo 101-8430Japan

Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently. In many applications, the data are supposed to have explicit or implicit structures. To develop efficient algorithms for such data, we have to propose possible structure models and test if the models are feasible. Hence, it is important to make a compact model for structured data, and enumerate all instances efficiently. There are few graph classes besides trees that can be used for a model. In this paper, we investigate distance-hereditary graphs. This class of graphs consists of isometric graphs and hence contains trees and cographs. First, a canonical and compact tree representation of the class is proposed. The tree representation can be constructed in linear time by using prefix trees. Usually, prefix trees are used to maintain a set of strings. In our algorithm, the prefix trees are used to maintain the neighborhood of vertices, which is a new approach unlike the lexicographically breadth-first search used in other studies. Based on the canonical tree representation, efficient algorithms for the distance-hereditary graphs are proposed, including linear time algorithms for graph recognition and graph isomorphism and an efficient enumeration algorithm. An efficient coding for the tree representation is also presented; it requires [3.59n] bits for a distance-hereditary graph of n vertices and 3n bits for a cograph. The results of coding improve previously known upper bounds （both are 2^O（nlogn）） of the number of distance-hereditary graphs and cographs to 2^[3.59n] and 2^3n, respectively.

关键词： algorithmic graph theory cograph distance-hereditary graph prefix tree tree representation

来源：评论

学校读者我要写书评

暂无评论

Parameterized certificate dispersal and its variants

引用

THEORETICAL COMPUTER SCIENCE 2016年 622卷 66-78页

作者： Garnero, Valentin Weller, Mathias Univ Montpellier 2 AIGCo Project Team LIRMM Montpellier France

Given a directed graph G and a set R of vertex pairs, the MINIMUM CERTIFICATE DISPERSAL problem asks for an assignment of arcs to vertices ("terminals") such that, for each (u, v) is an element of R, a u-v-path can be constructed using only arcs assigned to u or v. Herein, the total number k of assignments should be minimal. The problem is well motivated in key-exchange protocols for asymmetric cryptography. We provide a first parameterized complexity analysis of this NP-hard problem and its variant CHAINED MINIMUM CERTIFICATE DISPERSAL, where, instead of pairs of terminals, a set of paths ("chains") that should be constructed, is prescribed. Although polynomial-time solvable for constant values of k, the former variant seems much harder, surfacing in the proof that it is W[1]-hard with respect to k while CHAINED MINIMUM CERTIFICATE DISPERSAL yields a polynomial-size problem kernel. We even show fixed-parameter tractability of the latter with respect to the stronger parameter "number t of terminals". In particular, while there is no polynomial-size kernel with respect to t, the problem admits a polynomial-size Turing kernel. Towards answering the question whether MINIMUM CERTIFICATE DISPERSAL can be solved in polynomial time when t is constant, we show polynomial-time solvability for at most two requests (comprising all instances with t <= 2) using an algorithm for the STRONG DISTANCE problem, which asks for a minimum-size subdigraph in which two given vertices are strongly connected. Finally, we emphasize the hardness of MINIMUM CERTIFICATE DISPERSAL by proving it NP-hard for very restricted sets of instances, thereby excluding many parameters and combinations from consideration for efficient multivariate algorithms. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Asymmetric cryptography algorithmic graph theory Parameterized complexity Turing kernelization

来源：评论

学校读者我要写书评

暂无评论

Space efficient algorithms for directed series-parallel graphs

引用

JOURNAL OF ALGORITHMS 2006年第2期60卷 85-114页

作者： Jakoby, Andreas Liskiewicz, Maciej Reischuk, Ruediger Med Univ Lubeck Inst Theoret Informat D-23538 Lubeck Germany

The subclass of directed series-parallel graphs plays an important role in computer science. Whether a given graph is series-parallel is a well studied problem in algorithmic graph theory, for which fast sequential and parallel algorithms have been developed in a sequence of papers. Also methods are known to solve the reachability and the decomposition problem for series-parallel graphs time efficiently. However, no dedicated results have been obtained for the space complexity of these problems when restricted to series-parallel graphs - the topic of this paper. Deterministic algorithms are presented for the recognition, reachability, decomposition and the path counting problem for series-parallel graphs that use only logarithmic space. Since for arbitrary directed graphs reachability and path counting are believed not to be solvable in Logspace, the main contribution of this work are novel deterministic path finding routines that work correctly in series-parallel graphs, and a characterization of series-parallel graphs by forbidden subgraphs that can be tested space-efficiently. The space bounds are best possible, i.e. the decision problem is shown to be L-complete with respect to AC(0)-reductions. They have also implications for the parallel time complexity of these problems when restricted to series-parallel graphs. Finally, we sketch how these results can be generalized to extension of the series-parallel graph family: to graphs with multiple sources or multiple sinks and to the class of minimal vertex series-parallel graphs. (c) 2004 Elsevier Inc. All rights reserved.

关键词： efficient algorithms algorithmic graph theory computational complexity

来源：评论

学校读者我要写书评

暂无评论

A graph-Theoretic Approach to Scheduling in Cognitive Radio Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2015年第1期23卷 317-328页

作者： Gozupek, Didem Shalom, Mordechai Alagoz, Fatih Gebze Inst Technol Dept Comp Engn TR-41400 Kocaeli Turkey Tel Hai Coll Dept Comp Sci IL-12210 Upper Galilee Israel Bogazici Univ Dept Comp Engn TR-34342 Istanbul Turkey

We focus on throughput-maximizing, max-min fair, and proportionally fair scheduling problems for centralized cognitive radio networks. First, we propose a polynomial-time algorithm for the throughput-maximizing scheduling problem. We then elaborate on certain special cases of this problem and explore their combinatorial properties. Second, we prove that the max-min fair scheduling problem is NP-Hard in the strong sense. We also prove that the problem cannot be approximated within any constant factor better than 2 unless P = NP. Additionally, we propose an approximation algorithm for the max-min fair scheduling problem with approximation ratio depending on the ratio of the maximum possible data rate to the minimum possible data rate of a secondary users. We then focus on the combinatorial properties of certain special cases and investigate their relation with various problems such as the multiple-knapsack, matching, terminal assignment, and Santa Claus problems. We then prove that the proportionally fair scheduling problem is NP-Hard in the strong sense and inapproximable within any additive constant less than log(4/3). Finally, we evaluate the performance of our approximation algorithm for the max-min fair scheduling problem via simulations. This approach sheds light on the complexity and combinatorial properties of these scheduling problems, which have high practical importance in centralized cognitive radio networks.

关键词： algorithmic graph theory approximation algorithms cognitive radio networks dynamic spectrum access resource allocation scheduling

来源：评论

学校读者我要写书评

暂无评论

Laminar structure of ptolemaic graphs with applications

引用

DISCRETE APPLIED MATHEMATICS 2009年第7期157卷 1533-1543页

作者： Uehara, Ryuhei Uno, Yushi Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Osaka Japan

Ptolemaic graphs are those satisfying the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs. It can also be seen as a natural generalization of block graphs (and hence trees). In this paper, we first state a laminar structure of cliques, which leads to its canonical tree representation. This result is a translation of gamma-acyclicity which appears in the context of relational database schemes. The tree representation gives a simple intersection model of ptolemaic graphs, and it is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an efficient algorithm for the Hamiltonian cycle problem. (C) 2008 Elsevier B.V. All rights reserved.

关键词： algorithmic graph theory Data structures gamma-acyclicity Hamiltonian cycle Intersection model Ptolemaic graphs

来源：评论

学校读者我要写书评

暂无评论

Treewidth distance on phylogenetic trees

引用

THEORETICAL COMPUTER SCIENCE 2018年 731卷 99-117页

作者： Kelk, Steven Stamoulis, Georgios Wu, Taoyang Maastricht Univ Dept Data Sci & Knowledge Engn DKE Maastricht Netherlands Univ East Anglia Sch Comp Sci Norwich Norfolk England

In this article we study the treewidth of the display graph, an auxiliary graph structure obtained from the fusion of phylogenetic (i.e., evolutionary) trees at their leaves. Earlier work has shown that the treewidth of the display graph is bounded if the trees are in some formal sense topologically similar. Here we further expand upon this relationship. We analyze a number of reduction rules, commonly used in the phylogenetics literature to obtain fixed parameter tractable algorithms. In some cases (the subtree reduction) the reduction rules behave similarly with respect to treewidth, while others (the cluster reduction) behave very differently, and the behavior of the chain reduction is particularly intriguing because of its link with graph separators and forbidden minors. We also show that the gap between treewidth and Tree Bisection and Reconnect (TBR) distance can be infinitely large, and that unlike, for example, planar graphs the treewidth of the display graph can be as much as linear in its number of vertices. A number of other auxiliary results are given. We conclude with a discussion and list a number of open problems. (C) 2018 Elsevier B.V. All rights reserved.

关键词： graph theory Phylogenetics Treewidth algorithmic graph theory Computational biology

来源：评论

学校读者我要写书评

暂无评论

Tree independence number I. (Even hole, diamond, pyramid)-free graphs

引用

JOURNAL OF graph theory 2024年第4期106卷 923-943页

作者： Abrishami, Tara Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Vuskovic, Kristina Univ Hamburg Dept Math Hamburg Germany Univ Leeds Sch Comp Leeds England Princeton Univ Princeton NJ USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

The tree-independence number tree- alpha $\text{tree\unicode{x02010}}\alpha $, first defined and studied by Dallard, Milani & ccaron;, and & Scaron;torgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass C ${\mathscr{C}}$ of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that C ${\mathscr{C}}$ has bounded tree- alpha $\,\text{tree\unicode{x02010}}\,\alpha $. Via existing results, this yields a polynomial-time algorithm for the Maximum Weight Independent Set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milani & ccaron;, and & Scaron;torgel that in a hereditary graph class, tree- alpha $\,\text{tree\unicode{x02010}}\,\alpha $ is bounded if and only if the treewidth is bounded by a function of the clique number.

关键词： algorithmic graph theory even-hole-free graphs structural graph theory tree independence number treewidth

来源：评论

学校读者我要写书评

暂无评论

On computing longest paths in small graph classes

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2007年第5期18卷 911-930页

作者： Uehara, Ryuhei Uno, Yushi JAIST Sch Informat Sci Dept Informat Proc Ishikawa Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

The longest path problem is the one that finds a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes are known to be solved efficiently for the longest path problem. Among those, for trees, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for some tree-like graph classes by this approach. We next propose two new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on these classes.

关键词： algorithmic graph theory design and analysis of algorithms graph classes longest path problem

来源：评论

学校读者我要写书评

暂无评论

Fast canonical labeling of random subgraphs

引用

DOKLADY MATHEMATICS 2013年第2期87卷 178-180页

作者： Tikhomirov, M. I. Moscow MV Lomonosov State Univ Mech & Math Fac Moscow 119991 Russia

A well-known problem in algorithmic graph theory is the graph isomorphism problem. It consists in con-tructing an algorithm verifying whether two given graphs are isomorphic, i.e., whether it is possible to establish a bijective correspondence between the ver-tex sets of these graphs so that it induces a bijective correspondence between their edge sets (in other words, whether the vertices can be labeled so that the labeled graphs coincide).

关键词： Canonical Labeling graph theoryRandom Subgraphs algorithmic graph theory canonical labeling random subgraphs

来源：评论

学校读者我要写书评

暂无评论

Assisted Normative Reasoning with Aristotelian Diagrams 36

Assisted Normative Reasoning with Aristotelian Diagrams

引用

36th Annual International Conference on Legal Knowledge and Information Systems (JURIX)

作者： Hanauer, Kathrin Novotna, Tereza Pascucci, Matteo Univ Vienna Vienna Austria Masaryk Univ Brno Brno Czech Republic Slovak Acad Sci Bratislava Slovakia

ISBN: (纸本)9781643684727;9781643684734

We design a framework for assisted normative reasoning based on Aristotelian diagrams and algorithmic graph theory which can be employed to address heterogeneous tasks of deductive reasoning. Here we focus on two problems of normative determination: we show that the algorithms used to address these problems are computationally efficient and their operations are traceable by humans. Finally, we discuss an application of our framework to a scenario regulated by the GDPR.

关键词： algorithmic graph theory Aristotelian diagrams assisted reasoning automated deduction normative reasoning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：