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

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Bannach, Max Marwitz, Florian Andreas Tantau, Till European Space Agcy Adv Concepts Team Noordwijk Netherlands Univ Lubeck Inst Informat Syst Lubeck Germany Univ Lubeck Inst Theoret Comp Sci Lubeck Germany

ISBN: (纸本)9783959773119

The runtime of graph algorithms such as depth-first search or Dijkstra's algorithm is dominated by the fact that all edges of the graph need to be processed at least once, leading to prohibitive runtimes for large, dense graphs. We introduce a simple data structure for storing graphs (and more general structures) in a compressed manner using directed acyclic graphs (dags). We then show that numerous standard graph problems can be solved in time linear in the size of the dag compression of a graph, rather than in the number of edges of the graph. Crucially, many dense graphs, including but not limited to graphs of bounded twinwidth, have a dag compression of size linear in the number of vertices rather than edges. This insight allows us to improve the previous best results for the runtime of standard algorithms from quasi-linear to linear for the large class of graphs of bounded twinwidth, which includes all cographs, graphs of bounded treewidth, or graphs of bounded cliquewidth.

关键词： graph compression graph traversal twinwidth parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

On MAX-SAT with Cardinality Constraint 1

引用

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Panolan, Fahad Yaghoubizade, Hannane Univ Leeds Sch Comp Leeds W Yorkshire England Sharif Univ Technol Dept Math Sci Tehran Iran

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

We consider the weighted MAX-SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k-WMAX-SAT. This problem admits a (1 - 1/e)-factor approximation algorithm in polynomial time [Sviridenko, Algorithmica 2001] and it is proved that there is no (1 - 1/e + epsilon)-factor approximation algorithm in f(k) center dot n(o(k)) time for Maximum Coverage, the unweighted monotone version of k-WMAX-SAT [Manurangsi, SODA 2020]. Therefore, we study two restricted versions of the problem in the realm of parameterized complexity. 1. When the input is an unweighted 2-CNF formula (the problem is called k-MAX-2SAT), we design an efficient polynomial-size approximate kernelization scheme. That is, we design a polynomialtime algorithm that given a 2-CNF formula psi and epsilon > 0, compresses the input instance to a 2-CNF formula psi(star) such that any c-approximate solution of psi(star) can be converted to a c(1 - epsilon)-approximate solution of psi in polynomial time. 2. When the input is a planar CNF formula, i.e., the variable-clause incident graph is a planar graph, we show the following results: - There is an FPT algorithm for k-WMAX-SAT on planar CNF formulas that runs in 2(O(k)) center dot (C + V) time. - There is a polynomial-time approximation scheme for k-WMAX-SAT on planar CNF formulas that runs in time 2(O(1/epsilon))center dot k center dot (C + V). The above-mentioned C and V are the number of clauses and variables of the input formula respectively.

关键词： parameterized algorithms MAX-SAT MAX-2SAT

来源：评论

学校读者我要写书评

暂无评论

Block Elimination Distance 1

引用

47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： 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 LIRMM Montpellier France Univ Montpellier CNRS LIRMM Montpellier France

ISBN: (数字)9783030868383

ISBN: (纸本)9783030868376;9783030868383

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)))). The block elimination distance of a graph G to a graph class G is the minimum k such that G is an element of G((k)) and can be seen as an analog of the elimination distance parameter, defined in [J. Bulian & A. Dawar. Algorithmica, 75(2):363-382, 2016], with the difference that connectivity is now replaced by biconnectivity. We show that, for every non-trivial hereditary class G, the problem of deciding whether G. G(k) is NPcomplete. 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 of k 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. Our results are based on a structural characterization of the obstructions of B(G), relatively to the obstructions of G. 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 graphs. This yields the identification of all members O boolean AND G((k)), for every k is an element of N and every non-trivial minor-closed graph class G.

关键词： Elimination distance Graph minors Obstructions parameterized algorithms Biconnected graphs

来源：评论

学校读者我要写书评

暂无评论

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs 55

Network Sparsification for Steiner Problems on Planar and Bo...

引用

55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Pilipczuk, Marcin Pilipczuk, Michal Sankowski, Piotr van Leeuwen, Erik Jan Univ Bergen Dept Informat N-5020 Bergen Norway Univ Warsaw Inst Informat PL-00325 Warsaw Poland Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9781479965175

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k, uncovers a set F subset of E(G) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f. We apply this general theorem to prove that: given an unweighted graph G embedded on a surface of genus g and a terminal set S subset of V (G), one can in polynomial time find a set F subset of E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and vertical bar E(T)vertical bar;an analogous result holds for an optimal Steiner forest for a set S of terminal pairs;given an unweighted planar graph G and a terminal set S subset of V (G), one can in polynomial time find a set F subset of E(G) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S) and has size polynomial in vertical bar C vertical bar. In the language of parameterized complexity, these results imply the first polynomial kernels for STEINER TREE and STEINER FOREST on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (EDGE) MULTIWAY CUT on planar graphs (parameterized by the size of the cutset). STEINER TREE and similar "subset" problems were identified in [1] as important to the quest to widen the reach of the theory of bidimensionality [2, 3]. Therefore, our results can be seen as a leap forward to achieve this broader goal. Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an edge-weighted planar graph G, a designated face f bounded by a simple cycle of weight w(f), and an ac

关键词： Planar graphs Steiner Tree Steiner Forest (Edge) Multiway Cut polynomial kernel parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Corrigendum to “parameterized tractability of the maximum-duo preservation string mapping problem” [Theoret. Comput. Sci. 646 (2016) 16–25]

引用

Theoretical Computer Science 2016年 653卷 108-110页

作者： Stefano Beretta Mauro Castelli Riccardo Dondi Dipartimento di Informatica Sistemistica e Comunicazione Università degli Studi di Milano – Bicocca Milano Italy NOVA IMS Universidade Nova de Lisboa Lisboa Portugal Dipartimento di Lettere Filosofia e Comunicazione Università degli Studi di Bergamo Bergamo Italy

This is a corrigendum for our paper [1] , as we have found that the first FPT algorithm for the Maximum-Duo Preservation String Mapping Problem we presented is incorrect. However, we show that, by slightly modifying the color-coding technique on which the algorithm is based, we can fix the error, thus giving a correct FPT algorithm for Maximum-Duo Preservation String Mapping Problem.

关键词： Computational biology Common string partition parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Proportionally Fair Matching with Multiple Groups 1

引用

49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Inamdar, Tanmay Simonov, Kirill Portland State Univ Portland OR USA Univ Bergen Bergen Norway Univ Potsdam Hasso Plattner Inst Potsdam Germany

ISBN: (数字)9783031433801

ISBN: (纸本)9783031433795;9783031433801

We study matching problems with the notion of proportional fairness. Proportional fairness is one of the most popular notions of group fairness where every group is represented up to an extent proportional to the final selection size. Matching with proportional fairness or more commonly, proportionally fair matching, was introduced in [Chierichetti et al., AISTATS, 2019]. In this problem, we are given a graph G whose edges are colored with colors from a set C. The task is for given 0 <= alpha <= beta <= 1, to find a maximum (alpha, beta)-balanced matching M in G, that is a matching where for every color c is an element of C the number of edges in M of color c is between alpha|M| and beta|M|. Chierichetti et al. initiated the study of this problem with two colors and in the context of bipartite graphs only. However, in many practical applications, the number of colorsalthough often a small constant-is larger than two. In this work, we make the first step towards understanding the computational complexity of proportionally fair matching with more than two colors. We design exact and approximation algorithms achieving reasonable guarantees on the quality of the matching as well as on the time complexity, and our algorithms work in general graphs. Our algorithms are also supported by suitable hardness bounds.

关键词： Matching Fairness parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Time-Approximation Trade-Offs for Learning Bayesian Networks 12

Time-Approximation Trade-Offs for Learning Bayesian Networks

引用

12th International Conference on Probabilistic Graphical Models (PGM)

作者： Kundu, Madhumita Parviainen, Pekka Saurabh, Saket Univ Bergen Bergen Norway Univ Bergen Inst Math Sci Bergen Norway

Bayesian network structure learning is an NP-hard problem. Furthermore, the problem remains hard even for various subclasses of graphs. Motivated by the hardness of exact learning, we study approximation algorithms for learning Bayesian networks. First, we propose a moderately exponential time algorithm with running time O(2(l/kn)) that has an approximation ratio l/k where n is the number of vertices and l and k are user-defined parameters with l <= k. That is, we give time-approximation trade-offs for learning Bayesian networks. Second, we present a polynomial time algorithm with an approximation ratio 1/d to find an optimal graph whose connected components have size at most d

关键词： Bayesian Network Structure Learning parameterized algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Interprocedural Data-Flow Analysis Using Treedepth and Treewidth 1

引用

24th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI) part of the 50th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)

作者： Goharshady, Amir Kafshdar Zaher, Ahmed Khaled Hong Kong Univ Sci & Technol Clear Water Bay Hong Kong Peoples R China

ISBN: (数字)9783031249501

ISBN: (纸本)9783031249495;9783031249501

We consider interprocedural data-flow analysis as formalized by the standard IFDS framework, which can express many widelyused static analyses such as reaching definitions, live variables, and nullpointer. We focus on the well-studied on-demand setting in which queries arrive one-by-one in a stream and each query should be answered as fast as possible. While the classical IFDS algorithm provides a polynomialtime solution for this problem, it is not scalable in practice. More specifically, it will either require a quadratic-time preprocessing phase or takes linear time per query, both of which are untenable for modern huge codebases with hundreds of thousands of lines. Previous works have already shown that parameterizing the problem by the treewidth of the program's control-flow graph is promising and can lead to significant gains in efficiency. Unfortunately, these results were only applicable to the limited special case of same-context queries. In this work, we obtain significant speedups for the general case of on-demand IFDS with queries that are not necessarily same-context. This is achieved by exploiting a new graph sparsity parameter, namely the treedepth of the program's call graph. Our approach is the first to exploit the sparsity of control-flow graphs and call graphs at the same time and parameterize by both the treewidth and the treedepth. We obtain an algorithm with a linear preprocessing phase that can answer each query in constant time wrt the size of the input. Finally, our experimental results demonstrate that our approach significantly outperforms the classical IFDS and its on-demand variant.

关键词： Static analysis Data-flow analysis IFDS parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Lean Tree-Cut Decompositions: Obstructions and algorithms 36

Lean Tree-Cut Decompositions: Obstructions and Algorithms

引用

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Giannopoulou, Archontia C. Kwon, O-joung Raymond, Jean-Florent Thilikos, Dimitrios M. Tech Univ Berlin LaS Team Berlin Germany Incheon Natl Univ Dept Math Incheon South Korea Univ Montpellier CNRS LIRMM AlGCo Project Team Montpellier France

ISBN: (纸本)9783959771009

The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110: 47-66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1): 67-76, 1990]. This allows us to give, for every k is an element of N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.

关键词： tree-cut width lean decompositions immersions obstructions parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

The Treewidth of Smart Contracts 19

The Treewidth of Smart Contracts

引用

34th ACM/SIGAPP Annual International Symposium on Applied Computing (SAC)

作者： Chatterjee, Krishnendu Goharshady, Amir Kafshdar Goharshady, Ehsan Kafshdar IST Austria Klosterneuburg Austria Ferdowsi Univ Mashhad Mashhad Razavi Khorasan Iran

ISBN: (纸本)9781450359337

Smart contracts are programs that are stored and executed on the Blockchain and can receive, manage and transfer money (cryptocurrency units). Two important problems regarding smart contracts are formal analysis and compiler optimization. Formal analysis is extremely important, because smart contracts hold funds worth billions of dollars and their code is immutable after deployment. Hence, an undetected bug can cause significant financial losses. Compiler optimization is also crucial, because every action of a smart contract has to be executed by every node in the Blockchain network. Therefore, optimizations in compiling smart contracts can lead to significant savings in computation, time and energy. Two classical approaches in program analysis and compiler optimization are intraprocedural and interprocedural analysis. In intraprocedural analysis, each function is analyzed separately, while interprocedural analysis considers the entire program. In both cases, the analyses are usually reduced to graph problems over the control flow graph (CFG) of the program. These graph problems are often computationally expensive. Hence, there has been ample research on exploiting structural properties of CFGs for efficient algorithms. One such well-studied property is the treewidth, which is a measure of tree-likeness of graphs. It is known that intraprocedural CFGs of structured programs have treewidth at most 6, whereas the interprocedural treewidth cannot be bounded. This result has been used as a basis for many efficient intraprocedural analyses. In this paper, we explore the idea of exploiting the treewidth of smart contracts for formal analysis and compiler optimization. First, similar to classical programs, we show that the intraprocedural treewidth of structured Solidity and Vyper smart contracts is at most 9. Second, for global analysis, we prove that the interprocedural treewidth of structured smart contracts is bounded by 10 and, in sharp contrast with classical program

关键词： Smart Contracts parameterized algorithms Treewidth Blockchain Compiler Optimization Program Analysis Control Flow Graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：