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

Contraction Bidimensionality of Geometric Intersection Graphs

ALGORITHMICA 2022年第2期84卷 510-531页

作者： Baste, Julien Thilikos, Dimitrios M. Univ Lille CRIStAL Cent Lille Lille France Univ Montpellier CNRS LIRMM Montpellier France

Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Gamma(k). A graph class G has the SQGC property if every graph G is an element of G has treewidth O(bcg(G)(c)) for some 1 <= c < 2. The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQGC property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

关键词： Treewidth Bidimensionality parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Comparing temporal graphs using dynamic time warping

引用

SOCIAL NETWORK ANALYSIS AND MINING 2020年第1期10卷 1-16页

作者： Froese, Vincent Jain, Brijnesh Niedermeier, Rolf Renken, Malte Tech Univ Berlin Fac Algorithm & Computat Complex 4 Berlin Germany Tech Univ Berlin Fac Distributed Artificial Intelligence Lab 4 Berlin Germany

Within many real-world networks, the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to compare different temporal graphs. To this end, we propose to study dynamic time warping on temporal graphs. We define the dynamic temporal graph warping (dtgw) distance to determine the dissimilarity of two temporal graphs. Our novel measure is flexible and can be applied in various application domains. We show that computing the dtgw-distance is a challenging (in general) NP-hard optimization problem and identify some polynomial-time solvable special cases. Moreover, we develop a quadratic programming formulation and an efficient heuristic. In experiments on real-world data, we show that the heuristic performs very well and that our dtgw-distance performs favorably in de-anonymizing networks compared to other approaches.

关键词： Temporal graph matching Vertex signatures Heuristic optimization Quadratic programming parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for propositional model counting

引用

JOURNAL OF DISCRETE algorithms 2010年第1期8卷 50-64页

作者： Samer, Marko Szeider, Stefan Tech Univ Darmstadt Dept Comp Sci Darmstadt Germany Univ Durham Dept Comp Sci Durham England

We present algorithms for the propositional model counting problem #SAT. The algorithms utilize tree decompositions of certain graphs associated with the given CNF formula;in particular we consider primal, dual, and incidence graphs. We describe the algorithms coherently for a direct comparison and with sufficient detail for making an actual implementation reasonably easy. We discuss several aspects of the algorithms including worst-case time and space requirements. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Model counting Propositional satisfiability parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Block Elimination Distance

引用

GRAPHS AND COMBINATORICS 2022年第5期38卷 1-28页

作者： Diner, Oznur Yasar Giannopoulou, Archontia C. Stamoulis, Giannos Thilikos, Dimitrios M. Kadir Has Univ Comp Engn Dept Istanbul Turkey Univ Politecn Cataluna Dept Math Barcelona Spain Natl & Kapodistrian Univ Athens Dept Informat & Telecommun Athens Greece Univ Montpellier CNRS LIRMM Montpellier France

We introduce the parameter of block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class g, the class B(G) contains all graphs whose blocks belong to G and the class A(G) contains all graphs where the removal of a vertex creates a graph in G. Given a hereditary graph class G, we recursively define G((k)) so that G((0)) = B(G) and, if k >= 1 G((k)) B(A(G((k-1))) ) N We show that, for every nontrivial hereditary class g, the problem of deciding whether G is an element of G((k)) is NP-complete. We focus on the case where G is minor-closed and we study the minor obstruction set of G((k)) i.e., the minor-minimal graphs not in G((k)). We prove that the size of the obstructions of G((k)) is upper bounded by some explicit function ofk and the maximum size of a minor obstruction of G. This implies that the problem of deciding whether G is an element of G((k)) is constructively fixed parameter tractable, when parameterized by k. Finally, we give two graph operations that generate members of G((k)) from members of G((k -1)) and we prove that this set of operations is complete for the class O of outerplanar *** check and confirm if the authors Given and Family names have been correctly identified for author znur YaYar Diner. All authors names have been identified conectly. Please confirm if the corresponding author is correctly identified. Amend if *** is correct

关键词： Graph minors Block elimination distance Elimination distance Minor obstructions parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fixed parameter algorithms for ONE-SIDED CROSSING MINIMIZATION revisited

引用

JOURNAL OF DISCRETE algorithms 2008年第2期6卷 313-323页

作者： Dujmovic, Vida Fernau, Henning Kaufmann, Michael McGill Univ Dept Math & Stat Montreal PQ Canada Univ Trier FB IV Abt Informat D-54286 Trier Germany Univ Tubingen WSI Informat D-72076 Tubingen Germany

We exhibit a small problem kernel for the ONE-SIDED CROSSING MINIMIZATION problem. This problem plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we improve on the search tree algorithm developed in [V. Dujmovic, S. Whitesides, An efficient fixed parameter tractable algorithm for 1-sided crossing minimization, Algorithmica 40 (2004) 15-31] and derive an O(1.4656(k) + kn(2)) algorithm for this problem, where k upperbounds the number of tolerated edge crossings in the drawings of an n-vertex graph. (C) 2007 Elsevier B.V. All rights reserved.

关键词： Graph drawing Crossing minimization 2-layer drawings FPT parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploiting the Sparseness of Control-Flow and Call Graphs for Efficient and On-Demand Algebraic Program Analysis

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2023年第OOPSLA期7卷 1993–2022页

作者： Conrado, Giovanna Kobus Goharshady, Amir Kafshdar Kochekov, Kerim Tsai, Yun Chen Zaher, Ahmed Khaled Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Dept Math Clear Water Bay Hong Kong Peoples R China

Algebraic Program Analysis (APA) is a ubiquitous framework that has been employed as a unifying model for various problems in data-flow analysis, termination analysis, invariant generation, predicate abstraction and a wide variety of other standard static analysis tasks. APA models program summaries as elements of a regular algebra (A, circle plus, circle times, circle star, (o) over bar, (1) over bar). Suppose that a summary in A is assigned to every transition of the program and that we aim to compute the effect of running the program starting at line s and ending at line t. APA first computes a regular expression rho capturing all program paths of interest. In case of intraprocedural analysis, rho models all paths from s to t, whereas in the interprocedural case it models all interprocedurally-valid paths, i.e. paths that go back to the right caller function when a callee returns. This regular expression rho is then interpreted over the algebra (A, circle plus, circle times, circle star, (o) over bar, (1) over bar) to obtain the desired result. Suppose the program has n lines of code and each evaluation of an operation in the regular algebra takes O(k) time. It is well-known that a single APA query, or a set of queries with the same starting point B, can be answered in O (n . alpha(n) . k), where alpha is the inverse Ackermann function. In this work, we consider an on-demand setting for APA: the program is given in the input and can be preprocessed. The analysis has to then answer a large number of on-line queries, each providing a pair (s, t) of program lines which are the start and end point of the query, respectively. The goal is to avoid the significant cost of running a fresh APA instance for each query. Our main contribution is a series of algorithms that, after a lightweight preprocessing of O(n . lg n . k), answer each query in O(k) time. In other words, our preprocessing has almost the same asymptotic complexity as a single APA query, except for a sub-lo

关键词： Algebaric Program Analysis parameterized algorithms Graph Sparsity Treewidth Treedepth Data-flow Analysis

来源：评论

学校读者我要写书评

暂无评论

A Practical Approach to Courcelle's Theorem

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2009年第C期251卷 65-81页

作者： Kneis, Joachim Langer, Alexander Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany

In 1990, Courcelle showed that every problem definable in Monadic Second-Order Logic (MSO) can be solved in linear time on graphs with bounded treewidth. This powerful and important theorem is amongst others the foundation for several fixed parameter tractability results. The standard proof of Courcelle's Theorem is to construct a finite bottom-up tree automaton that recognizes a tree decomposition of the graph. However, the size of the automaton, which is usually hidden as a constant in the Landau-notation, can become extremely large and cannot be bounded by any elemental function unless P = NP (Frick and Grohe, 2004). This makes the problem hard to tackle in practice, because it is just impossible to construct the tree automata. Aiming for a practical implementation, we give a proof of Courcelle's Theorem restricted to Extended MSO formulas of the form opt U subset of V phi( U), where phi is a first-order formula with vocabulary (adj, U) and opt is an element of{min, max}. Note that many optimization problems such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set can be expressed by such formulas. The proof uses a new technique based on using Hintikka game properties in dynamic programming. To demonstrate the usability of this approach, we present an implementation that solves such formulas on graphs with small pathwidth. It turns out that the large constants can be circumvented on graphs that are not too complex.

关键词： Exact algorithms parameterized algorithms Treewidth Model-Checking Monadic Second-Order Logic Courcelle's Theorem

来源：评论

学校读者我要写书评

暂无评论

The Bounded Pathwidth of Control-Flow Graphs

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2023年第OOPSLA期7卷 292–317页

作者： Conrado, Giovanna Kobus Goharshady, Amir Kafshdar Lam, Chun Kit Hong Kong Univ Sci & Technol Dept Math Dept Comp Sci & Engn Clear Water Bay Hong Kong Peoples R China

Pathwidth and treewidth are standard and well-studied graph sparsity parameters which intuitively model the degree to which a given graph resembles a path or a tree, respectively. It is well-known that the control-flow graphs of structured goto-free programs have a tree-like shape and bounded treewidth. This fact has been exploited to design considerably more efficient algorithms for a wide variety of static analysis and compiler optimization problems, such as register allocation, mu-calculus model-checking and parity games, data-flow analysis, cache management, and liftetime-optimal redundancy elimination. However, there is no bound in the literature for the pathwidth of programs, except the general inequality that the pathwidth of a graph is at most O (lg n) times its treewidth, where n is the number of vertices of the graph. In this work, we prove that control-flow graphs of structured programs have bounded pathwidth and provide a linear-time algorithm to obtain a path decomposition of small width. Specifically, we establish a bound of 2 center dot d on the pathwidth of programs with nesting depth d. Since real-world programs have small nesting depth, they also have bounded pathwidth. This is significant for a number of reasons: (i) pathwidth is a strictly stronger parameter than treewidth, i.e. any graph family with bounded pathwidth has bounded treewidth, but the converse does not hold;(ii) any algorithm that is designed with treewidth in mind can be applied to bounded-pathwidth graphs with no change;(iii) there are problems that are fixed-parameter tractable with respect to pathwidth but not treewidth;(iv) verification algorithms that are designed based on treewidth would become significantly faster when using pathwidth as the parameter;and (v) it is easier to design algorithms based on bounded pathwidth since one does not have to consider the often-challenging case of merge nodes in treewidth-based dynamic programming. Thus, we invite the static analysis and

关键词： Control-flow Graphs parameterized algorithms Pathwidth Treewidth

来源：评论

学校读者我要写书评

暂无评论

A faster parameterized algorithm for temporal matching

引用

INFORMATION PROCESSING LETTERS 2022年 174卷

作者： Zschoche, Philipp Tech Univ Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

A temporal graph is a sequence of graphs (called layers) over the same vertex set-describing a graph topology which is subject to discrete changes over time. A Delta-temporal matching M is a set of time edges (e, t) (an edge e paired up with a point in timet) such that for all distinct time edges (e, t), (e', t') is an element of M we have that e and e' do not share an endpoint, or the time-labels t and t' are at least Delta time units apart. Mertzios et al. [STACS'20] provided a 2(O(Delta nu)).vertical bar G vertical bar(O(1))-time algorithm to compute the maximum size of a Delta-temporal matching in a temporal graph G, where vertical bar G vertical bar denotes the size of G, and nu is the Delta-vertex cover number of G. The Delta-vertex cover number is the minimum number nu such that the classical vertex cover number of the union of any Delta consecutive layers of the temporal graph is upper-bounded by nu. We show an improved algorithm to compute a Delta-temporal matching of maximum size with a running time of Delta(O(nu)).vertical bar G vertical bar and hence provide an exponential speedup in terms of Delta. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Temporal graphs Delta-windows parameterized algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized analysis and crossing minimization problems

引用

COMPUTER SCIENCE REVIEW 2022年第0期45卷

作者： Zehavi, Meirav Ben Gurion Univ Negev Beer Sheva Israel

In this survey/introductory article, we first present the basics of the field of parameterized Complexity, made accessible to readers without background on the subject. Afterwards, we survey some central questions in Graph Drawing that concern the analysis of crossing minimization problems from the viewpoint of parameterized analysis, as well as put forward some of the remaining challenges. This article originated from an invited talk given at the 29th International Symposium on Graph Drawing and Network Visualization. (C) 2022 Elsevier Inc. All rights reserved.

关键词： Crossing minimization parameterized Complexity parameterized algorithms Graph Drawing Kernelization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：