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

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

来源：评论

学校读者我要写书评

暂无评论

Matchings under distance constraints I

引用

ANNALS OF OPERATIONS RESEARCH 2021年第1-2期305卷 137-161页

作者： Madarasi, Peter Eotvos Lorand Univ Dept Operat Res Budapest Hungary

This paper introduces the d-distance matching problem, in which we are given a bipartite graph G = (S, T;E) with S = {s(1),..., s(n)}, a weight function on the edges and an integer d epsilon Z(+). The goal is to find a maximum-weight subset M subset of E of the edges satisfying the following two conditions: (i) the degree of every node of S is at most one in M, (ii) if s(i) t, s (j) t. M, then vertical bar j - i vertical bar= d. This question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple 3-approximation. We give an FPT algorithm parameterized by d and also showthat the casewhen the size of T is constant can be solved in polynomial time. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most 2- 1/2d-1, and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial (2- 1/d)-approximation algorithm is also presented. Several greedy approaches are considered, and a local search algorithm is described that achieves an approximation ratio of 3/2 + epsilon for any constant epsilon > 0 in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest.

关键词： Distance matching Restricted b-matching Constrained matching Scheduling parameterized algorithms Approximation algorithms Integrality gap

来源：评论

学校读者我要写书评

暂无评论

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年 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

来源：评论

学校读者我要写书评

暂无评论

A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph

引用

INFORMATION PROCESSING LETTERS 2021年 171卷

作者： Ohsaka, Naoto NEC Corp Ltd Kawasaki Kanagawa 2118666 Japan

We consider the problem of counting the number of vertices reachable from each vertex in a digraph G, which is equal to computing all the out-degrees of the transitive closure of G. The current (theoretically) fastest algorithms run in quadratic time;however, Borassi has shown that this problem is not solvable in truly subquadratic time unless the Strong Exponential Time Hypothesis fails [Borassi, 2016 [13]]. In this paper, we present an O(f(3)n)-time exact algorithm, where n is the number of vertices in G and f is the feedback edge number of G. Our algorithm thus runs in truly subquadratic time for digraphs of f = O(f(1/3-epsilon)) for any epsilon > 0, i.e., the number of edges is n plus O(f(1/3-epsilon)), and is filly polynomial fixed parameter tractable, the notion of which was first introduced by Fomin et al. (2018) [22]. We also show that the same result holds for vertex-weighted digraphs, where the task is to compute the total weights of vertices reachable from each vertex. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Reachability Transitive closure parameterized algorithms FPT in P

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of finding minimum bounded chains

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2024年 122卷

作者： Blaser, Nello Brun, Morten Salbu, Lars M. Vagset, Erlend Raa Univ Bergen Dept Informat Bergen Norway Univ Bergen Dept Math Bergen Norway Univ Bergen Ctr Data Sci Bergen Norway Western Norway Univ Appl Sci Dept Comp Sci Elect Engn & Math Sci Forde Norway

Finding the smallest d-chain with a specific (d - 1)-boundary in a simplicial complex is known as the Minimum Bounded Chain problem (MBCd). MBCd is NP-hard for all d >= 2. In this paper, we prove that it is also W[1]-hard for all d >= 2, if we parameterize the problem by solution size. We also give an algorithm solving MBC1 in polynomial time and introduce and implement two fixed parameter tractable (FPT) algorithms solving MBCd for all d. The first algorithm uses a shortest path approach and is parameterized by solution size and coface degree. The second algorithm is a dynamic programming approach based on treewidth, which has the same runtime as a lower bound we prove under the exponential time hypothesis.(c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license(http://***/licenses/by/4.0/).

关键词： Minimum bounded chain Computational topology parameterized algorithms Complexity theory Topological data analysis Treewidth

来源：评论

学校读者我要写书评

暂无评论

A parameterized Measure-and-Conquer Analysis for Finding a k-Leaf Spanning Tree in an Undirected Graph

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2014年第1期16卷 179-200页

作者： Binkele-Raible, Daniel Fernau, Henning Univ Trier Abt Informat Wissensch Trier Germany

The problem of finding a spanning tree in an undirected graph with a maximum number of leaves is known to be NP-hard. We present an algorithm which finds a spanning tree with at least k leaves in time O*(3.4575(k)) which improves the currently best algorithm. The estimation of the running time is done by using a non-standard measure. The present paper is one of the still few examples that employ the Measure & Conquer paradigm of algorithm analysis in the area of parameterized Algorithmics.

关键词： parameterized algorithms measure-and-conquer analysis maximum leaf spanning tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：