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

Solving NP-hard problems on GATEx graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets

引用

THEORETICAL COMPUTER SCIENCE 2024年 1037卷

作者： Hellmuth, Marc Scholz, Guillaume E. Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Leipzig Dept Comp Sci & Interdisciplinary Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany

The class of GAlled-Tree Explainable (GATEx) graphs has recently been discovered as a natural generalization of cographs. Cographs are precisely those graphs that can be uniquely represented by a rooted tree where the leaves correspond to the vertices of the graph. As a generalization, GATEx graphs are precisely those that can be uniquely represented by a particular rooted acyclic network, called a galled-tree. This paper explores the use of galled-trees to solve combinatorial problems on GATEx graphs that are, in general, NP-hard. We demonstrate that finding a maximum clique, an optimal vertex coloring, a perfect order, as well as a maximum independent set in GATEx graphs can be efficiently done in linear time. The key idea behind the linear-time algorithms is to utilize the galled-trees that explain the GATEx graphs as a guide for computing the respective cliques, colorings, perfect orders, or independent sets.

关键词： Modular decomposition Galled-tree Cograph NP-hard problems linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

linear Kernels and linear-time algorithms for Finding Large Cuts

引用

ALGORITHMICA 2018年第9期80卷 2574-2615页

作者： Etscheid, Michael Mnich, Matthias Univ Bonn Inst Informat Bonn Germany Maastricht Univ Dept Quantitat Econ Maastricht Netherlands

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:We show that an algorithm by Crowston et al. (Algorithmica 72(3):734-757, 2015) for (Signed) Max-Cut Above Edwards-Erd A s Bound can be implemented so as to run in linear time;this significantly improves the previous analysis with run time . We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erd A s Bound with O(k) vertices, improving a kernel with vertices by Crowston et al. (Theor Comput Sci 513:53-64, 2013). We improve all known kernels for parameterizations above strongly -extendible properties (a generalization of the Max-Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) from vertices to O(k) vertices. Therefore, Max Acyclic Subdigraph parameterized above Poljak-Turzik bound admits a kernel with O(k) vertices and can be solved in time;this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012).

关键词： Max-cut Kernelization linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Simple linear-time algorithms for counting independent sets in distance-hereditary graphs

引用

DISCRETE APPLIED MATHEMATICS 2018年 239卷 144-153页

作者： Lin, Min-Sheng Natl Taipei Univ Technol Dept Elect Engn Taipei 106 Taiwan

A connected graph is distance-hereditary if any two vertices have the same distance in all of its connected induced subgraphs. This paper proposes a unified method for designing linear-time algorithms for counting independent sets and their two variants, independent dominating sets and independent perfect dominating sets, in distance-hereditary graphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distance-hereditary graphs Counting problem Independent sets Independent dominating sets Independent perfect dominating sets linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in linear time

引用

ALGORITHMICA 2023年第9期85卷 2605-2666页

作者： Didimo, Walter Kaufmann, Michael Liotta, Giuseppe Ortali, Giacomo Univ Perugia Dept Engn Perugia Italy Univ Tubingen Tubingen Germany

A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series-parallel graphs. Our linear-time algorithm is based on a characterization of the planar series-parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take;the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph.

关键词： Orthogonal drawings Bend minimization linear-time algorithms Plane graphs Series-parallel graphs

来源：评论

学校读者我要写书评

暂无评论

Structured Watermarks for Structured Software

引用

SN Computer Science 2024年第5期5卷 1-10页

作者： Bento, Lucila M. S. Boccardo, Davidson R. Machado, Raphael C. S. Pereira de Sá, Vinícius G. Szwarcfiter, Jayme L. State University of Rio de Janeiro São Francisco Xavier St. RJ Rio de Janeiro 20550-000 Brazil Federal University of Rio de Janeiro Athos da Silveira Ramos Ave RJ Rio de Janeiro 21941-916 Brazil Fluminense Federal University Gal. Milton Tavares de Souza Ave RJ Niterói 24210-310 Brazil Albert Einstein Israelite Hospital Brigadeiro Faria Lima Ave SP São Paulo 01451-001 Brazil

Software watermarking involves integrating an identifier within the software, enabling timely retrieval to disclose authorship/ownership, and deter piracy. Various software watermarking schemes have been proposed in the literature, many of which involve statically embedding an encoded identifier into the control flow graph of the program. In this paper, we propose novel embedding and extraction algorithms characterized by four key features: randomization, generating watermarks with a size closely matching the number of bits in the identifier, implementing both encoding and decoding with linear time complexity, and, most importantly, generating watermarks that conform to structured code. We emphasize the capability to encode the same identifier as distinct graphs, coupled with the absence of cumbersome “GOTO”-like substructures, as enhancements to the stealthiness of our watermarks. This feature makes them more resilient to common forms of attack, contributing to their effectiveness in safeguarding software integrity and discouraging unauthorized use. © The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. 2024.

关键词： linear-time algorithms Software watermarking Structured code

来源：评论

学校读者我要写书评

暂无评论

Decremental optimization of vertex-colouring under the reconfiguration framework

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY 2023年第1期8卷 80-92页

作者： Yanagisawa, Yusuke Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Japan

Suppose that we are given a positive integer k, and a k-(vertex-)colouring f 0 of a given graph G. Then we are asked to find a colouring of G using the minimum number of colours among colourings that are reachable from f 0 by iteratively changing a colour assignment of exactly one vertex while maintaining the property of k-colourings. In this paper, we give linear-time algorithms to solve the problem for graphs of degeneracy at most two and for the case where k = 3 . These results imply linear-time algorithms for series-parallel graphs and grid graphs. In addition, we give linear-time algorithms for chordal graphs and cographs. On the other hand, we show that, for any k = 4 , this problem remains NP-hard for planar graphs with degeneracy three and maximum degree four. Thus, we obtain a complexity dichotomy for this problem with respect to the degeneracy of a graph and the number k of colours.

关键词： Combinatorial reconfiguration graph algorithms graph colouring linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

On cherry-picking and network containment

引用

THEORETICAL COMPUTER SCIENCE 2021年 856卷 121-150页

作者： Janssen, Remie Murakami, Yukihiro Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands

Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks. In particular, one needs to distinguish different networks and determine whether one network is contained in another. In this paper, we introduce cherry-picking networks, a class of networks that can be reduced by a so-called cherry-picking sequence. We then show how to compare such networks using their sequences. We characterize reconstructible cherry-picking networks, which are the networks that are uniquely determined by the sequences that reduce them, making them distinguishable. Furthermore, we show that a cherry-picking network is contained in another cherry picking network if a sequence for the latter network reduces the former network, provided both networks can be reconstructed from their sequences in a similar way (i.e., they are in the same reconstructible class). Lastly, we show that the converse of the above statement holds for tree-child networks, thereby showing that NETWORK CONTAINMENT, the problem of checking whether a network is contained in another, can be solved by computing cherry picking sequences in linear time for tree-child networks. (C) 2020 The Author(s). Published by Elsevier B.V.

关键词： Phylogenetic networks Network containment Cherry-picking sequences Tree containment linear-time algorithms Cherry-picking networks

来源：评论

学校读者我要写书评

暂无评论

The Power of linear-time Data Reduction for Maximum Matching

引用

ALGORITHMICA 2020年第12期82卷 3521-3565页

作者： Mertzios, George B. Nichterlein, Andre Niedermeier, Rolf Univ Durham Dept Comp Sci Durham England TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m root n) time;however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

关键词： Maximum-cardinality matching Bipartite graphs linear-time algorithms Kernelization Parameterized complexity analysis FPT in P

来源：评论

学校读者我要写书评

暂无评论

Folding Every Point on a Polygon Boundary to a Point

引用

algorithms 2023年第6期16卷 281-281页

作者： Phetmak, Nattawut Fakcharoenphol, Jittat Kasetsart Univ Fac Comp Engn Bangkok 10900 Thailand

We consider a problem in computational origami. Given a piece of paper as a convex polygon P and a point f located within, we fold every point on a boundary of P to f and compute a region that is safe from folding, i.e., the region with no creases. This problem is an extended version of a problem by Akitaya, Ballinger, Demaine, Hull, and Schmidt that only folds corners of the polygon. To find the region, we prove structural properties of intersections of parabola-bounded regions and use them to devise a linear-time algorithm. We also prove a structural result regarding the complexity of the safe region as a variable of the location of point f, i.e., the number of arcs of the safe region can be determined using the straight skeleton of the polygon P.

关键词： geometric folding parabola intersection computational origami linear-time algorithms straight skeletons

来源：评论

学校读者我要写书评

暂无评论

New sharp lower bound for the quorum coloring number of trees

引用

INFORMATION PROCESSING LETTERS 2022年 178卷

作者： Sahbi, Rafik Algiers Higher Sch Appl Sci Dept Preparatory Training BP 474Martyrs Sq Algiers 16001 Algeria

A partition;= {V1, V2, ..., Vk} of the vertex set V of a graph G into k color classes Vi, with 1 < i < k is called a quorum coloring if for every vertex v is an element of V, at least half of the vertices in the closed neighborhood N[v] of v have the same color as v. The maximum cardinality of a quorum coloring of G is called the quorum coloring number of G and is denoted by *q(G). A quorum coloring of order *q(G) is a *q-coloring. In this paper, we partially answer an open problem concerning quorum colorings of graphs. Namely, we improve a sharp lower bound given in 2012 by Eroh and Gera on the quorum coloring number of a nontrivial tree, and show that our new lower bound can be computed in linear time. Moreover, we show that this bound is attained by all non trivial binary trees. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Defensive alliances Matchings Binary trees algorithms linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：