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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary graph Classes

Quasi-Polynomial Time Techniques for Independent Set and Bey...

引用

作者： Gartland, Peter University of California Santa Barbara

学位级别：Ph.D., Doctor of Philosophy

An independent set in a graph G is a collection of vertices with no edge between any two. The Independent Set problem is a classic NP-Hard problem that takes in a graph G and the task is to find an independent set in G of maximum size. An induced subgraph of G is another graph, H, where the vertex set of H is a subset V (H) ⊆ V (G), and the edge set of H is all edges uv in E(G) where u, v ∈ V (H). A graph is said to be H-free if it does not contain H as an induced subgraph. Lastly, quasi-polynomial functions are functions that grow (slightly) faster than polynomial functions by allowing poly-log terms in their exponents, for example, n log2(n) is a quasi-polynomial function. In this thesis, we will provide a quasi-polynomial time algorithm for Independent Set on Pk-free graphs, where Pk denotes a path with k vertices. We will later extend this result in multiple ways. First, we give a quasi-polynomial time algorithm for Independent Set as well as related problems, such as Feedback Vertex Set on C>k-free graphs, which are graphs that do not contain induced cycles with more than k vertices. Additionally, we will give a quasi-polynomial time algorithm for Independent Set on H-free graphs where H is a forest of paths and subdivided claws. A subdivided claw is a graph formed by taking three paths of any desired length along with a vertex v that is a neighbor of exactly one end vertex in each of the three paths. This last result resolves an open problem first investigated by Alekseev in *** a seemingly different research thread, we will characterize graph classes with few minimal separators. A minimal separator is a set S such that there are two vertices u, v in different components of G − S and for any proper subset S ′ ⊂ S, u and v are in the same component of G − S ′ . A class F of graphs is called tame if every graph in F on n vertices contains at most n O(1) minimal separators, quasi-tame if every graph in F on n vertices contains at mostn logO(1)(n) minimal sepa

关键词： algorithmic graph theory Algorithms graph theory Independent set Quasi-tame graph classes

来源：评论

学校读者我要写书评

暂无评论

Deterministic Small Vertex Connectivity in Almost Linear Time 63

Deterministic Small Vertex Connectivity in Almost Linear Tim...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Saranurak, Thatchaphol Yingchareonthawornchai, Sorrachai Univ Michigan Ann Arbor MI 48109 USA Aalto Univ Espoo Finland

ISBN: (纸本)9781665455190

In the vertex connectivity problem, given an undirected n-vertex m-edge graph G, we need to compute the minimum number of vertices that can disconnect G after removing them. This problem is one of the most well-studied graph problems. From 2019, a new line of work [Nanongkai et al. STOC'19;SODA'20;STOC'21] has used randomized techniques to break the quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm via the recently announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow FOCS'00] takes O(m( n + min{c(5/2), cn(3/4)})) time where c is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant c > 3. In this paper, we give the first deterministic almost-linear time vertex connectivity algorithm for all constants c. Our running time is m(1+o(1))2(O( c2)) time, which is almost-linear for all c = o(root log n). This is the first deterministic algorithm that breaks the O(n(2))-time bound on sparse graphs where m = O(n), which is known for more than 50 years ago [Kleitman'69]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almost-linear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlstrom [FOCS'12] requires large polynomial time and is randomized.

关键词： algorithmic graph theory Vertex Connectivity

来源：评论

学校读者我要写书评

暂无评论

Vertex Connectivity in Poly-logarithmic Max-Flows 2021

Vertex Connectivity in Poly-logarithmic Max-Flows

引用

53rd Annual ACM SIGACT Symposium on theory of Computing (STOC)

作者： Li, Jason Nanongkai, Danupon Panigrahi, Debmalya Saranurak, Thatchaphol Yingchareonthawornchai, Sorrachai Carnegie Mellon Univ Pittsburgh PA 15213 USA Univ Copenhagen Copenhagen Denmark KTH Stockholm Sweden Duke Univ Durham NC 27706 USA Univ Michigan Ann Arbor MI 48109 USA Aalto Univ Espoo Finland

ISBN: (纸本)9781450380539

The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in (O) over tilde (m(alpha)) time for any alpha >= 1, if there is a m(alpha)-time maxflow algorithm. Using the current best maxflow algorithm that runs in m(4/3+o(1)) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m(4/3+o(1) )- time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an (O) over tilde (mn)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time was known before our work, even if we assume an (O) over tilde (m)-time maxflow algorithm. Our new technique is robust enough to also improve the best (O) over tilde (mn)-time bound for directed vertex connectivity to mn(1-1/12+o(1)) time.

关键词： algorithmic graph theory vertex connectivity

来源：评论

学校读者我要写书评

暂无评论

MAYGEN: an open-source chemical structure generator for constitutional isomers based on the orderly generation principle

引用

JOURNAL OF CHEMINFORMATICS 2021年第1期13卷 48-48页

作者： Yirik, Mehmet Aziz Sorokina, Maria Steinbeck, Christoph Friedrich Schiller Univ Inst Inorgan & Analyt Chem Lessing Str 8 D-07743 Jena Germany

The generation of constitutional isomer chemical spaces has been a subject of cheminformatics since the early 1960s, with applications in structure elucidation and elsewhere. In order to perform such a generation efficiently, exhaustively and isomorphism-free, the structure generator needs to ensure the building of canonical graphs already during the generation step and not by subsequent filtering. Here we present MAYGEN, an open-source, pure-Java development of a constitutional isomer molecular generator. The principles of MAYGEN's architecture and algorithm are outlined and the software is benchmarked in single-threaded mode against the state-of-the-art, but closed-source solution MOLGEN, as well as against the best open-source solution PMG. Based on the benchmarking, MAYGEN is on average 47 times faster than PMG and on average three times slower than MOLGEN in performance.

关键词： Constitutional isomer generation algorithmic group theory algorithmic graph theory Chemical graph generation Open-source software CDK

来源：评论

学校读者我要写书评

暂无评论

Editorial for the Special Issue on "Algorithms for graphs and Networks"

引用

ALGORITHMS 2020年第11期13卷 292页

作者： Lewis, Rhyd Cardiff Univ Sch Math Cardiff CF24 4AG Wales

Experiments on a large set of real-world public transport networks are also included, helping to illustrate the performance of these methods. In the second article, Thiruvady, Blum and Ernst use a resource constrained job scheduling problem to help test a variety of different hybrid algorithms that combine elements of heuristics and mathematical programming [2]. [...]they develop a multiobjective beam search and ant colony optimisation hybrid that uses problem-specific bounds to help guide the search towards feasibility.

关键词： graphs and networks algorithmic graph theory combinatorial optimisation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Surjective H-Colouring over Reflexive Digraphs

引用

ACM TRANSACTIONS ON COMPUTATION theory 2019年第1期11卷 3-3页

作者： Larose, Benoit Martin, Barnaby Paulusma, Daniel Univ Quebec Montreal LACIM CP 8888Succursale Ctr Ville Montreal PQ H3C 3P8 Canada Univ Durham Dept Comp Sci Durham England

The SURJECTIVE H-COLOURING problem is to test if a given graph allows a vertex-SURJECTIVE homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are automorphisms, as a means to obtain complexity-theoretic classifications of SURJECTIVE H-COLOURING in the case of reflexive digraphs. Chen (2014) proved, in the setting of constraint satisfaction problems, that SURJECTIVE H-COLOURING is NP-complete if H has the property that all of its polymorphisms are essentially unary. We give the first concrete application of his result by showing that every endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for SURJECTIVE H-COLOURING when H is a reflexive tournament: if H is transitive, then SURJECTIVE H-COLOURING is in NL;otherwise, it is NP-complete. By combining this result with some known and new results, we obtain a complexity classification for SURJECTIVE H-COLOURING when H is a partially reflexive digraph of size at most 3.

关键词： Surjective H-Coloring computational complexity algorithmic graph theory universal algebra constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

Surjective H-Colouring over Reflexive Digraphs 35

Surjective H-Colouring over Reflexive Digraphs

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Larose, Benoit Martin, Barnaby Paulusma, Daniel Univ Quebec Montreal LACIM Montreal PQ Canada Univ Durham Dept Comp Sci Durham England

ISBN: (纸本)9783959770620

The SURJECTIVE H-COLOURING problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are automorphisms, as a means to obtain complexity-theoretic classifications of SURJECTIVE H-COLOURING in the case of reflexive digraphs. Chen [2014] proved, in the setting of constraint satisfaction problems, that SURJECTIVE H-COLOURING is NP-complete if H has the property that all of its polymorphisms are essentially unary. We give the first concrete application of his result by showing that every endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for SURJECTIVE H-COLOURING when H is a reflexive tournament: if H is transitive, then SURJECTIVE H-COLOURING is in NL, otherwise it is NP-complete. By combining this result with some known and new results we obtain a complexity classification for SURJECTIVE H-COLOURING when H is a partially reflexive digraph of size at most 3.

关键词： Surjective H-Coloring Computational Complexity algorithmic graph theory Universal Algebra Constraint Satisfaction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：