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

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

来源：评论

学校读者我要写书评

暂无评论

Canonizing graphs of Bounded Tree Width in Logspace 33

Canonizing Graphs of Bounded Tree Width in Logspace

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Elberfeld, Michael Schweitzer, Pascal Rhein Westfal TH Aachen Aachen Germany

ISBN: (纸本)9783959770019

graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized in deterministic logarithmic space (logspace). This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous classes of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.

关键词： algorithmic graph theory computational complexity graph isomorphism logspace tree width

来源：评论

学校读者我要写书评

暂无评论

Canonizing graphs of Bounded Tree Width in Logspace

引用

ACM TRANSACTIONS ON COMPUTATION theory 2017年第3期9卷 12-12页

作者： Elberfeld, Michael Schweitzer, Pascal Rhein Westfal TH Aachen Aachen Germany Rhein Westfal TH Aachen Lehrstuhl Informat 7 D-52056 Aachen Germany

graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized by logarithmic-space (logspace) algorithms. This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous class of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.

关键词： algorithmic graph theory computational complexity graph canonization graph isomorphism logspace algorithms tree width

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Tree Path Labeling of Hypergraphs - A Generalization of the Consecutive Ones Property 1

Tree Path Labeling of Hypergraphs - A Generalization of the ...

引用

1st International Conference on Algorithms and Discrete Applied Mathematics (CALDAM)

作者： Narayanaswamy, N. S. Srinivasan, Anju Indian Inst Technol Madras 600036 Tamil Nadu India

ISBN: (纸本)9783319149745;9783319149738

Given a set system F subset of (2(U)\empty set) of a finite set U of cardinality n and a tree T of size n, does there exist at least one bijection phi : U -> V (T) such that for each S is an element of F, the set {phi(x) vertical bar x is an element of S} is the vertex set of a path in T ? Our main result is that the existence of such a bijection from U to V (T) is equivalent to the existence of a function l from F to the set of all paths in T such that for any three, not necessarily distinct, S-1, S-2, S-3 is an element of F, vertical bar S-1 boolean AND S-2 boolean AND S-3 vertical bar = vertical bar l (S-1) boolean AND l (S-2) boolean AND l (S-3)vertical bar. l is referred to as a tree path labeling of F.

关键词： consecutive ones property algorithmic graph theory hypergraph isomorphism interval labeling

来源：评论

学校读者我要写书评

暂无评论

Boolean-Valued Models of Telecommunication Systems in Some Problems of Network Security

Boolean-Valued Models of Telecommunication Systems in Some P...

引用

International Siberian Conference on Control and Communications (SIBCON)

作者： Shcherba, E. V. Omsk State Tech Univ OmSTU Omsk Russia

ISBN: (纸本)9781479971039

The paper describes an approach to modeling telecommunication systems and processes of data transmission based on Boolean-valued networks. Models to address two specific problems of network security are offered. It is possible to adapt existing algorithms of graph theory to apply them in this approach. Thus, it becomes possible to take into account not only quantitative but also qualitative measure of information in solving urgent network problems. A definition of a maximum flow in Boolean-valued networks and an algorithm to find this flow were proposed. Two examples to demonstrate the described models and algorithms are also presented in the paper.

关键词： Boolean-valued networks network security algorithmic graph theory shorthest path maximum flow

来源：评论

学校读者我要写书评

暂无评论

Embedding and Canonizing graphs of Bounded Genus in Logspace 14

Embedding and Canonizing Graphs of Bounded Genus in Logspace

引用

46th Annual ACM Symposium on theory of Computing (STOC)

作者： Elberfeld, Michael Kawarabayashi, Ken-ichi Rhein Westfal TH Aachen Aachen Germany Natl Inst Informat Tokyo Japan JST ERATO Kawarabayashi Large Graph Project Tokyo Japan

ISBN: (纸本)9781450327107

graph embeddings of bounded Euler genus (that means, embeddings with bounded orientable or nonorientable genus) help to design time-efficient algorithms for many graph problems. Since linear-time algorithms are known to compute embeddings of any bounded Euler genus, one can always assume to work with embedded graphs and, thus, obtain fast algorithms for many problems on any class of graphs of bounded Euler genus. Problems on graphs of bounded Euler genus are also important from the perspective of finding space-efficient algorithms, mostly focusing on problems related to finding paths and matchings in graphs. So far, known space-bounded approaches needed the severe assumption that an embedding is given as part of the input since no space-efficient embedding procedure for nonplanar graphs was known. The present work sidesteps this assumption and shows that embeddings of any bounded Euler genus can be computed in deterministic logarithmic space (logspace);allowing to generalize results on the space complexity of path and matching problems from embedded graphs to graphs of bounded Euler genus. The techniques developed for the embedding procedure also allow to compute canonical representations and, thus, solve the isomorphism problem for graphs of bounded Euler genus in logspace.

关键词： computational complexity theory algorithmic graph theory logspace isomorphism graph embedding Euler genus

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On Evolutionary Algorithms for Large Cliques in Random graphs

引用

INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS & STATISTICS 2011年第S11期22卷 53-60页

作者： Javidi, Mohammad M. Mehrabi, Saeed Shahid Bahonar Univ Kerman Dept Comp Sci Kerman Iran

The maximum clique problem (MCP) is an old NP-complete problem which has been frequently used for delivering the NP-completeness of many other problems with respect to computational complexity literature. In this paper, we give a heuristic based genetic algorithm for solving this problem. By incorporating a heuristic into the crossover operator, we speed up the convergence rate of our algorithm - GACP (genetic algorithm for clique problem). GACP has been tested on a variety of challenging benchmarks including DIMACS instances and compared with two recently efficient algorithms. Experimental results show that GACP not only competes consistently with these algorithms but also performed well at solving the maximum clique problem.

关键词： algorithmic graph theory Combinatorial Optimization Maximum Clique Problem

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：