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

The Directed Steiner Network problem is tractable for a constant number of terminals

SIAM JOURNAL ON COMPUTING 2006年第2期36卷 543-561页

作者： Feldman, Jon Ruhl, Matthias Columbia Univ New York NY 10027 USA Google Mountain View CA 94043 USA MIT Cambridge MA 02139 USA

We consider the Directed Steiner Network problem, also called the POINT-TO-POINT CONNECTION problem. Given a directed graph G and p pairs {(s(1), t(1)),..., (s(p), t(p))} of nodes in the graph, one has to find the smallest subgraph H of G that contains paths from s(i) to t(i) for all i. The problem is NP-hard for general p, since the DIRECTED STEINER Tree problem is a special case. Until now, the complexity was unknown for constant p >= 3. We prove that the problem is polynomially solvable if p is any constant number, even if nodes and edges in G are weighted and the goal is to minimize the total weight of the subgraph H. In addition, we give an efficient algorithm for the STRONGLY CONNECTED STEINER SUBGRAPH problem for any constant p, where given a directed graph and p nodes in the graph, one has to compute the smallest strongly connected subgraph containing the p nodes.

关键词： Steiner tree Steiner network network design directed graphs polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial-time decomposition algorithms for support vector machines

引用

MACHINE LEARNING 2003年第1期51卷 51-71页

作者： Hush, D Scovel, C Los Alamos Natl Lab Los Alamos NM 87545 USA

This paper studies the convergence properties of a general class of decomposition algorithms for support vector machines (SVMs). We provide a model algorithm for decomposition, and prove necessary and sufficient conditions for stepwise improvement of this algorithm. We introduce a simple "rate certifying" condition and prove a polynomial-time bound on the rate of convergence of the model algorithm when it satisfies this condition. Although it is not clear that existing SVM algorithms satisfy this condition, we provide a version of the model algorithm that does. For this algorithm we show that when the slack multiplier C satisfies root1/2 less than or equal to Cless than or equal to mL, where m is the number of samples and L is a matrix norm, then it takes no more than 4LC(2)m(4)/epsilon iterations to drive the criterion to within epsilon of its optimum.

关键词： support vector machines polynomial-time algorithms decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

Periodic constraint satisfaction problems: Tractable subclasses

引用

CONSTRAINTS 2005年第2期10卷 97-113页

作者： Chen, HB Univ Pompeu Fabra Dept Tecnol Barcelona Spain

We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.

关键词： periodic problems polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Periodic constraint satisfaction problems: Tractable subclasses

Periodic constraint satisfaction problems: Tractable subclas...

引用

9th International Conference on Principles and Practice of Constraint Programming

作者： Chen, HB Univ Pompeu Fabra Dept Tecnol Barcelona Spain

关键词： periodic problems polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Bi-arc graphs and the complexity of list homomorphisms

引用

JOURNAL OF GRAPH THEORY 2003年第1期42卷 61-80页

作者： Feder, T Hell, P Huang, J Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3P4 Canada

Given graphs G, H, and lists L(v) subset of or equal to V(H), v is an element of V(G), a list homomorphism of G to H with respect to the lists L is a mapping f: V(G) --> V(H) such that uv is an element of E(G) implies f(u)f(v) is an element of E(H), and f(v) is an element of (v) for all v is an element of V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) subset of or equal to V(H), v is an element of V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and (H) over bar is a circular arc graph, and is NP-complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi-arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi-arc graph, and is NP-complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. (C) 2002 Wiley Periodicals, Inc.

关键词： list colorings list homomorphisms internal graphs circular arc graphs bi-arc graphs edge asteroids sheet width polynomial-time algorithms NP-completeness complexity

来源：评论

学校读者我要写书评

暂无评论

An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique

引用

INFORMATION PROCESSING LETTERS 2002年第6期83卷 315-321页

作者： Low, CP Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

Random Duplicated Assignment (RDA) is an approach in which video data is stored by assigning a number of copies of each data block to different, randomly chosen disks. It has been shown that this approach results in smaller response times and lower disk and RAM costs compared to the well-known disk stripping techniques. Based on this storage approach, one has to determine, for each given batch of data blocks, from which disk each of the data blocks is to be retrieved. This is to be done in such a way that the maximum load of the disks is minimized. The problem is called the Retrieval Selection Problem (RSP). In this paper, we propose a new efficient algorithm for RSP. This algorithm is based on the breadth-first search approach and is able to guarantee optimal solutions for RSP in O(n(2) + mn), where m and n correspond to the number of data blocks and the number of disks, respectively. We will show that our proposed algorithm has a lower time complexity than an existing algorithm, called the MFS algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： random duplicated assignment breadth-first search polynomial-time algorithms load balancing algorithms

来源：评论

学校读者我要写书评

暂无评论

Extracting minimal siphon-traps of Petri nets and its application to computing nonnegative integer-invariants

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2002年第11期E85A卷 2436-2446页

作者： Taoka, S Takano, K Watanabe, T Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan Hitachi Software Engn Co Yokohama Kanagawa Japan

A siphon-trap of a Petri net N is defined as a place set S with S-. = S-., where S-.={u\ N has an edge from u to a vertex of S} and S-. = {v\ N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: 1. FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net;2. FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. 3. STFM-T (STFM-T-i, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.

关键词： Petri nets minimal siphon-traps Fourier-Motzkin method invariant computation polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for linear programming over algebraic extensions

引用

ALGORITHMICA 2001年第4期31卷 459-478页

作者： Beling, PA Univ Virginia Dept Syst Engn Charlottesville VA 22903 USA

We study the computational complexity of linear programs with coefficients that are real algebraic numbers under a Turing machine model of computation. After reviewing a method for exact representation of algebraic numbers under the Turing model, we show that the fundamental tasks of comparison and arithmetic can be performed in polynomial time. Our technique for establishing polynomial-time algorithms for comparison and arithmetic is distinct from the usual resultant-based approaches, and has the advantage that it provides a natural framework for analysis of the complexity of computational tasks, such as Gaussian elimination, that involve a sequence of arithmetic operations. Our main contribution is to show that a variant of the ellipsoid method can be used to solve linear programming in time polynomial in the encoding size of the problem coefficients and the degree of any algebraic extension that contains those coefficients.

关键词： linear programming algebraic numbers computational complexity symbolic computation ellipsoid method polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期262卷 161-189页

作者： DasGupta, B Sontag, ED Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA Rutgers State Univ Dept Math New Brunswick NJ 08903 USA

This paper presents a polynomial-time algorithm for equivalence under certain semiring congruences. These congruences arise when studying the isomorphism of state spaces for a class of hybrid systems. The area of hybrid systems concerns issues of modeling, computation, and control for systems which combine discrete and continuous components. The subclass of piecewise linear (PL) systems provides one systematic approach to discrete-time hybrid systems, naturally blending switching mechanisms with classical linear components. PL systems model arbitrary interconnections of finite automata and linear systems. Tools from automata theory, logic, and related areas of computer science and finite mathematics are used in the study of PL systems, in conjunction with linear algebra techniques, all in the context of a "PL algebra" formalism. PL systems are of interest as controllers as well as identification models. Basic questions for any class of systems are those of equivalence, and, in particular, whether state spaces are equivalent under a change of variables. This paper studies this state-space equivalence problem for PL systems. The problem was known to be decidable, but its computational complexity was potentially exponential;here it is shown to be solvable in polynomial time. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： hybrid systems piecewise-linear systems state-space equivalence semiring congruences polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for finding regular simple paths in outerplanar graphs

引用

JOURNAL OF algorithms 2000年第2期35卷 235-259页

作者： Nedev, ZP Wood, PT Univ Cape Town Dept Comp Sci ZA-7700 Rondebosch South Africa Kings Coll London Dept Comp Sci London WC2R 2LS England

Let G be a labeled directed graph with are labels drawn from alphabet Sigma, R be a regular expression over Sigma, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of are labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time. (C) 2000 Academic Press.

关键词： labeled directed graphs NP-completeness polynomial-time algorithms regular expressions simple paths outerplanar graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：