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

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

来源：评论

学校读者我要写书评

暂无评论

Full Characterization of a Class of Graphs Tailored for Software Watermarking

引用

ALGORITHMICA 2019年第7期81卷 2899-2916页

作者： Bento, Lucila M. S. Boccardo, Davidson R. Machado, Raphael C. S. Pereira de Sa, Vinicius G. Szwarcfiter, Jayme L. Univ Fed Rio de Janeiro Rio De Janeiro Brazil Inst Nac Metrol Qualidade & Tecnol Rio De Janeiro Brazil

Digital watermarks have been regarded as a promising way to fight copyright violations in the software industry. In some graph-based watermarking schemes, identification data is disguised as control-flow graphs of dummy code. Recently, Chroni and Nikolopoulos proposed an ingenious such scheme whereby an integer is encoded into a particular kind of permutation graph. We give a formal characterization of the class of graphs generated by their encoding function, which we call canonical reducible permutation graphs. A linear-time recognition algorithm is also given, setting the basis for a polynomial-time algorithm to restore watermarks that underwent the malicious removal of some edges. Finally, we give a simpler decoding algorithm for Chroni and Nikolopoulos' watermarks.

关键词： linear-time algorithms Reducible permutation graphs Digital watermarking Software security

来源：评论

学校读者我要写书评

暂无评论

Forest-like abstract Voronoi diagrams in linear time

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2018年 68卷 134-145页

作者： Bohler, Cecilia Klein, Rolf Lingas, Andrzej Liu, Chih-Hung Univ Bonn Inst Comp Sci 1 Bonn Germany Lund Univ Dept Comp Sci Lund Sweden

The Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. [1] we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V (S) is a tree, and for each subset S' subset of S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V (S) inside D can be constructed in linear time. (c) 2017 Elsevier B.V. All rights reserved.

关键词： Voronoi diagrams General distance Abstract Voronoi diagrams linear-time algorithms Forest structures

来源：评论

学校读者我要写书评

暂无评论

On the resilience of canonical reducible permutation graphs

引用

DISCRETE APPLIED MATHEMATICS 2018年 234卷 32-46页

作者： Bento, Lucila M. S. Boccardo, Davidson R. Machado, Raphael C. S. Pereira de Sa, Vinicius G. Szwarcfiter, Jayme Luiz Univ Fed Rio de Janeiro Inst Matemat Rio De Janeiro Brazil Inst Nacl Metrol Qualidade & Tecnol Rio De Janeiro Brazil Univ Fed Rio de Janeiro COPPE Sistemas Rio De Janeiro Brazil

An ingenious graph-based watermarking scheme recently proposed by Chroni and Nikolopoulos encodes integers as a special type of reducible permutation graphs. It was claimed without proof that those graphs can withstand attacks in the form of a single edge removal. We introduce a linear-time algorithm which restores the original graph after removals of k <= 2 edges, therefore proving an even stronger result. Furthermore, we prove that k <= 5 general edge modifications (removals/insertions) can always be detected in polynomial time. Both bounds are tight. Our results reinforce the interest in regarding Chroni and Nikolopoulos's scheme as a possible software watermarking solution for numerous applications. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Reducible permutation graphs Graph-based watermarking linear-time algorithms Software security

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter algorithms for DAG Partitioning

引用

DISCRETE APPLIED MATHEMATICS 2017年 220卷 134-160页

作者： van Bevern, Rene Bredereck, Robert Chopin, Morgan Hartung, Sepp Hueffner, Falk Nichterlein, Andre Suchy, Ondfej Novosibirsk State Univ Novosibirsk Russia TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ Ulm Inst Optimierung & Operat Res D-89069 Ulm Germany Czech Tech Univ Fac Informat Technol Prague Czech Republic

Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. (2009) as DAG PARTITIONING: given an arc-weighted directed acyclic graph on n vertices and m arcs, delete arcs with total weight at most k such that each resulting weakly-connected component contains exactly one sink-a vertex without outgoing arcs. DAG PARTITIONING iS NP-hard. We show an algorithm to solve DAG PARTITIONING in O(2(k) . (n m)) time, that is, in linear time for fixed k. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG PARTITIONING CM simulated citation networks within five minutes for k <= 190 and m being 10(7) and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.'s heuristic. We show that Leskovec et al.'s heuristic works optimally on trees and generalize this result by showing that DAG PARTITIONING is solvable in 2(0(t2)) " n time if a width-t tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian (2012). We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction. (C) 2016 Elsevier B.V. All rights reserved.

关键词： NP-hard problem Graph algorithms Polynomial-time data reduction Multiway cut linear-time algorithms Algorithm engineering Evaluating heuristics

来源：评论

学校读者我要写书评

暂无评论

Online Matroid Intersection: Beating Half for Random Arrival 19th

Online Matroid Intersection: Beating Half for Random Arrival

引用

19th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Guruganesh, Guru Prashanth Singla, Sahil Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9783319592503;9783319592497

For two matroids M-1 and M-2 defined on the same ground set E, the online matroid intersection problem is to design an algorithm that constructs a large common independent set in an online fashion. The algorithm is presented with the ground set elements one-by-one in a uniformly random order. At each step, the algorithm must irrevocably decide whether to pick the element, while always maintaining a common independent set. While the natural greedy algorithm-pick an element whenever possible-is half competitive, nothing better was previously known;even for the special case of online bipartite matching in the edge arrival model. We present the first randomized online algorithm that has a 1/2 + delta competitive ratio in expectation, where delta > 0 is a constant. The expectation is over the random order and the coin tosses of the algorithm. As a corollary, we also obtain the first linear time algorithm that beats half competitiveness for offline matroid intersection.

关键词： Online algorithms Matroid intersection Randomized algorithms Competitive analysis linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Counting spanning trees using modular decomposition

引用

THEORETICAL COMPUTER SCIENCE 2014年 526卷 41-57页

作者： Nikolopoulos, Stavros D. Palios, Leonidas Papadopoulos, Charis Univ Ioannina Dept Comp Sci & Engn GR-45110 Ioannina Greece Univ Ioannina Dept Math GR-45110 Ioannina Greece

In this paper we present an algorithm for determining the number of spanning trees of a graph G which takes advantage of the structure of the modular decomposition tree of G. Specifically, our algorithm works by contracting the modular decomposition tree of the input graph G in a bottom-up fashion until it becomes a single node;then, the number of spanning trees of G is computed as the product of a collection of values which are associated with the vertices of G and are updated during the contraction process. In particular, when applied on a (q, q - 4)-graph for fixed q, a P-4-tidy graph, or a tree-cograph, our algorithm computes the number of its spanning trees in time linear in the size of the graph, where the complexity of arithmetic operations is measured under the uniform-cost criterion. Therefore we give the first linear-time algorithm for the counting problem in the considered graph classes. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Number of spanning trees Modular decomposition Kirchhoff matrix tree theorem linear-time algorithms (q, q-4)-graph P-4-tidy graph Tree-cograph

来源：评论

学校读者我要写书评

暂无评论

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions

引用

THEORETICAL COMPUTER SCIENCE 2009年第1期410卷 1-15页

作者： Heggernes, Pinar Papadopoulos, Charis Univ Bergen Dept Informat N-5020 Bergen Norway

We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute. (C) 2008 Published by Elsevier B.V.

关键词： linear-time algorithms Minimal completions of graphs Minimal deletions of graphs Graph classes

来源：评论

学校读者我要写书评

暂无评论

linear-time Algorithm for the Paired-Domination Problem in Convex Bipartite Graphs

引用

THEORY OF COMPUTING SYSTEMS 2012年第4期50卷 721-738页

作者： Hung, Ruo-Wei Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 41349 Taiwan

A bipartite graph G=(U,W,E) with vertex set V=Ua(a)W is convex if there exists an ordering of the vertices of W such that for each uaU, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound.

关键词： Graph algorithms linear-time algorithms Paired-domination Total domination Convex bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

Minimal separators in extended P₄-laden graphs

引用

DISCRETE APPLIED MATHEMATICS 2012年第18期160卷 2769-2777页

作者： Pedrotti, Vagner de Mello, Celia Picinin Univ Estadual Campinas Inst Comp Campinas SP Brazil Univ Fed Mato Grosso do Sul Fac Comp Campo Grande Brazil

In this paper, we use the primeval decomposition tree to compute the minimal separators of some graphs and to describe a linear-time algorithm that lists the minimal separators of extended P-4-laden graphs, extending an algorithm for P-4-sparse graphs given by Nikolopoulos and Palios [S.D. Nikolopoulos, L Palios, Minimal separators in P-4-sparse graphs, Discrete Math. 306 (3) (2006) 381-392]. We also give bounds on the number and total size of all minimal separators of extended P-4-laden graphs and some of their subclasses, such as P-4-tidy and P-4-lite graphs. Moreover, we show that these bounds are tight for all subclasses considered. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Minimal separators Primeval decomposition Modular decomposition Graphs with few P-4's linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：