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

ALGORITHMICA 1991年第6期6卷 826-839页

作者： MASUYAMA, S IBARAKI, T KYOTO UNIV FAC ENGNDEPT APPL MATH & PHYSKYOTO 606JAPAN

This paper discusses the complexity of packing k-chains (simple paths of length k) into an undirected graph;the chains packed must be either vertex-disjoint or edge-disjoint. linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general and k = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three and k = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four and k = 3.

关键词： GRAPH algorithms COMPUTATIONAL COMPLEXITY GRAPH PACKING CHAIN PACKING linear-time algorithms NP-COMPLETENESS

来源：评论

学校读者我要写书评

暂无评论

All structured programs have small tree width and good register allocation

引用

INFORMATION AND COMPUTATION 1998年第2期142卷 159-181页

作者： Thorup, M Univ Copenhagen Dept Comp Sci DK-2100 Copenhagen Denmark

The register allocation problem for an imperative program is often modeled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a flow graph G is the intersection graph of some connected subgraphs of G. These connected subgraphs represent the lives, or life times, of variables, so the coloring problem models that two variables with overlapping life times should be in different registers. For general programs with unrestricted gotos, the interference graph can be any graph, and hence we cannot in general color within a factor O(n(epsilon)) from optimality unless NP = P. It is shown that if a graph has tree width k, we can efficiently color any intersection graph of connected subgraphs within a factor ([k/2]+1) from optimality. Moreover, it is shown that structured (=goto-free) programs, including, for example, short circuit evaluations and multiple exits from loops, have tree width at most 6. Thus, for every structured program, we can do register allocation efficiently within a factor 4 from optimality, regardless of how many registers are needed. The bounded tree decomposition may be derived directly from the parsing of a structured program, and it implies that the many techniques for bounded tree width may now be applied in compiler optimization, solving problems in linear time that are NP-hard, or even P-space hard, for general graphs. (C) 1998 Academic Press.

关键词： linear-time algorithms Decomposable graphs Complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 967-975页

作者： Asdre, Katerina Nikolopoulos, Stavros D. Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece

We study a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short. Given a graph G and a subset T of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint paths P that covers the vertices of G such that the k vertices of T are all endpoints of the paths in P. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality;note that, if T is empty (or, equivalently, k = 0), the stated problem coincides with the classical path cover problem. The kPC problem generalizes some path cover related problems, such as the 1HP and 2HP problems, which have been proved to be NP-complete. Note that the complexity status for both 1HP and 2HP problems on interval graphs remains an open question (Damaschke ( 1993)[9]). In this paper, we show that the kPC problem can be solved in linear time on the class of proper interval graphs, that is, in O(n + m) time on a proper interval graph on n vertices and m edges. The proposed algorithm is simple, requires linear space. and also enables us to solve the 1HP and 2HP problems on proper interval graphs within the same time and space complexity. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Perfect graphs Proper interval graphs Path cover Fixed-endpoint path cover linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimum-weight spanning tree algorithms -: A survey and empirical study

引用

COMPUTERS & OPERATIONS RESEARCH 2001年第8期28卷 767-785页

作者： Bazlamaçci, CF Hindi, KS Brunel Univ Dept Syst Engn Uxbridge UB8 3PH Middx England Middle E Tech Univ Dept Elect & Elect Engn TR-06531 Ankara Turkey

The minimum-weight spanning tree problem is one of the most typical and well-known problems of combinatorial optimisation. Efficient solution techniques had been known for many years. However, in the last two decades asymptotically faster algorithms have been invented. Each new algorithm brought the time bound one step closer to linearity and finally Karger, Klein and Tarjan proposed the only known expected linear-time method. Modern algorithms make use of more advanced data structures and appear to be more complicated to implement. Most authors and practitioners refer to these but still use the classical ones, which are considerably simpler but asymptotically slower. The paper first presents a survey of the classical methods and the more recent algorithmic developments. Modern algorithms are then compared with the classical ones and their relative performance is evaluated through extensive empirical tests, using reasonably large-size problem instances. Randomly generated problem instances used in the tests range from small networks having 512 nodes and 1024 edges to quite large ones with 16384 nodes and 524288 edges. The purpose of the comparative study is to investigate the conjecture that modern algorithms are also easy to apply and have constants of proportionality small enough to make them competitive in practice with the older ones.

关键词： network optimisation graph algorithms minimum spanning tree linear-time algorithms performance evaluation

来源：评论

学校读者我要写书评

暂无评论

AN OPTIMAL GREEDY HEURISTIC TO COLOR INTERVAL-GRAPHS

引用

INFORMATION PROCESSING LETTERS 1991年第1期37卷 21-25页

作者： OLARIU, S Department of Computer Science Old Dominion University Norfolk VA 23529-0162 USA

We characterize interval graphs in terms of a certain linear order on their vertex set. It turns out that with this linear order, the well-known greedy heuristic "always use the smallest available color" yields an exact coloring algorithm for interval graphs. In addition, the heuristic can be implemented to run in linear time.

关键词： COLORING HEURISTICS INTERVAL GRAPHS linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

引用

ALGORITHMICA 2010年第3期58卷 679-710页

作者： Asdre, Katerina Nikolopoulos, Stavros D. Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T of k vertices of V (G), a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint paths P that covers the vertices of G such that the k vertices of T are all endpoints of the paths in P. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality;note that, if T is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112: 4964, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.

关键词： Perfect graphs Interval graphs Path cover Fixed-endpoint path cover linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：