The Experts below are selected from a list of 150 Experts worldwide ranked by ideXlab platform
Pascal Van Hentenryck - One of the best experts on this subject based on the ideXlab platform.
-
ls Graph Tree a local search framework for constraint optimization on Graphs and Trees
ACM Symposium on Applied Computing, 2009Co-Authors: Pham Quang Dung, Yves Deville, Pascal Van HentenryckAbstract:LS(Graph & Tree) is a local search framework which aims at simplifying the modeling of Constraint Satisfaction Optimization Problems on Graphs (CSOP on Graphs or GCSOP). Optimum Constrained Trees (OCT) problems (a subclass of CSOP on Graphs) in which we need to find an optimum subTree with additional constraints of a given weighted Graph arise in many real-life applications. This paper introduces the LS(Graph & Tree) framework and local search abstractions for OCT problems. These abstractions are applied to model and solve the edge weighted k-Cardinality Tree (KCT) problem. The modeling as well as experimental results show the significance of the abstractions.
-
SAC - LS(Graph & Tree): a local search framework for constraint optimization on Graphs and Trees
Proceedings of the 2009 ACM symposium on Applied Computing - SAC '09, 2009Co-Authors: Pham Quang Dung, Yves Deville, Pascal Van HentenryckAbstract:LS(Graph & Tree) is a local search framework which aims at simplifying the modeling of Constraint Satisfaction Optimization Problems on Graphs (CSOP on Graphs or GCSOP). Optimum Constrained Trees (OCT) problems (a subclass of CSOP on Graphs) in which we need to find an optimum subTree with additional constraints of a given weighted Graph arise in many real-life applications. This paper introduces the LS(Graph & Tree) framework and local search abstractions for OCT problems. These abstractions are applied to model and solve the edge weighted k-Cardinality Tree (KCT) problem. The modeling as well as experimental results show the significance of the abstractions.
Carl Sechen - One of the best experts on this subject based on the ideXlab platform.
-
a unified approach to the approximate symbolic analysis of large analog integrated circuits
IEEE Transactions on Circuits and Systems I-regular Papers, 1996Co-Authors: Qicheng Yu, Carl SechenAbstract:This paper describes a unified approach to the approximate symbolic analysis of large linearized analog circuits in the complex frequency domain. It combines two new approximation-during-computation strategies with a variation of the classical two-Graph Tree enumeration method. The first strategy is to generate common Trees of the two-Graphs, and therefore the product terms in the symbolic network function, in the decreasing order of magnitude. This is made possible by our algorithm for generating color-constrained spanning Trees in the order of weight. It avoids the burden of computing all the product terms only to find most of them numerically negligible. The second approximation strategy is the sensitivity-based simplification of two-Graphs, which excludes from the two-Graphs many of the insignificant circuit elements that have little effect on the network function being derived. It significantly reduces the complexity of the two-Graphs before Tree enumeration. Our approach is therefore able to symbolically analyze much larger analog integrated circuits than previously reported, using complete small signal models for the semiconductor devices. We show accurate yet reasonably sized symbolic network functions for integrated circuits with up to 39 transistors whereas previous approaches were limited to less than 15. For even larger circuits, the limit is imposed mainly by the interpretability of the generated symbolic network function.
-
approximate symbolic analysis of large analog integrated circuits
International Conference on Computer Aided Design, 1994Co-Authors: Qicheng Yu, Carl SechenAbstract:This paper describes a unified approach to the approximate symbolic analysis of large linearized analog circuits. It combines two new approximation-during-computation strategies with a variation of the classical two-Graph Tree enumeration method. The first strategy is to generate common Trees of the two-Graphs, and therefore the product terms in the symbolic network function, in the decreasing order of magnitude. The second approximation strategy is the sensitivity-based simplification of two-Graphs, which excludes from the two-Graphs many circuit elements that have little effect on the network function being derived. Our approach is therefore able to symbolically analyze much larger analog integrated circuits than previously reported, using complete small signal models for the semiconductor devices. We show accurate yet reasonably sized symbolic network functions for integrated circuits with up to 39 transistors whereas previous approaches were limited to less than 15.
Liming Cai - One of the best experts on this subject based on the ideXlab platform.
-
Rapid ab initio prediction of RNA pseudoknots via Graph Tree decomposition.
Journal of mathematical biology, 2007Co-Authors: Jizhen Zhao, Russell L. Malmberg, Liming CaiAbstract:The prediction of RNA secondary structure including pseudoknots remains a challenge due to the intractable computation of the sequence conformation from nucleotide interactions under free energy models. Optimal algorithms often assume a restricted class for the predicted RNA structures and yet still require a high-degree polynomial time complexity, which is too expensive to use. Heuristic methods may yield time-efficient algorithms but they do not guarantee optimality of the predicted structure. This paper introduces a new and efficient algorithm for the prediction of RNA structure with pseudoknots for which the structure is not restricted. Novel prediction techniques are developed based on Graph Tree decomposition. In particular, based on a simplified energy model, stem overlapping relationships are defined with a Graph, in which a specialized maximum independent set corresponds to the desired optimal structure. Such a Graph is Tree decomposable; dynamic programming over a Tree decomposition of the Graph leads to an efficient optimal algorithm. The final structure predictions are then based on re-ranking a list of suboptimal structures under a more comprehensive free energy model. The new algorithm is evaluated on a large number of RNA sequence sets taken from diverse resources. It demonstrates overall sensitivity and specificity that outperforms or is comparable with those of previous optimal and heuristic algorithms yet it requires significantly less time than the compared optimal algorithms.
-
WABI - Rapid ab initio RNA folding including pseudoknots via Graph Tree decomposition
Lecture Notes in Computer Science, 2006Co-Authors: Jizhen Zhao, Russell L. Malmberg, Liming CaiAbstract:The prediction of RNA secondary structure including pseudoknots remains a challenge due to the intractable computation of the sequence conformation from intriguing nucleotide interactions. Optimal algorithms often assume a restricted class for the predicted RNA structures and yet still require a high-degree polynomial time complexity, which is too expensive to use. Heuristic methods may yield time-efficient algorithms but they do not guarantee optimality of the predicted structure. This paper introduces a new and efficient algorithm for the prediction of RNA structure with pseudoknots for which the structure is not restricted. Novel prediction techniques are developed based on Graph Tree decomposition. In particular, stem overlapping relationships are defined with a Graph, in which a specialized maximum independent set (IS) corresponds to the desired optimal structure. Such a Graph is Tree decomposable; dynamic programming over a Tree decomposition of the Graph leads to an efficient algorithm. The new algorithm is evaluated on a large number of RNA sequence sets taken from diverse resources. It demonstrates overall sensitivity and specificity that outperforms or is comparable with those of previous optimal and heuristic algorithms yet it requires significantly less time than other optimal algorithms.
Pham Quang Dung - One of the best experts on this subject based on the ideXlab platform.
-
ls Graph Tree a local search framework for constraint optimization on Graphs and Trees
ACM Symposium on Applied Computing, 2009Co-Authors: Pham Quang Dung, Yves Deville, Pascal Van HentenryckAbstract:LS(Graph & Tree) is a local search framework which aims at simplifying the modeling of Constraint Satisfaction Optimization Problems on Graphs (CSOP on Graphs or GCSOP). Optimum Constrained Trees (OCT) problems (a subclass of CSOP on Graphs) in which we need to find an optimum subTree with additional constraints of a given weighted Graph arise in many real-life applications. This paper introduces the LS(Graph & Tree) framework and local search abstractions for OCT problems. These abstractions are applied to model and solve the edge weighted k-Cardinality Tree (KCT) problem. The modeling as well as experimental results show the significance of the abstractions.
-
SAC - LS(Graph & Tree): a local search framework for constraint optimization on Graphs and Trees
Proceedings of the 2009 ACM symposium on Applied Computing - SAC '09, 2009Co-Authors: Pham Quang Dung, Yves Deville, Pascal Van HentenryckAbstract:LS(Graph & Tree) is a local search framework which aims at simplifying the modeling of Constraint Satisfaction Optimization Problems on Graphs (CSOP on Graphs or GCSOP). Optimum Constrained Trees (OCT) problems (a subclass of CSOP on Graphs) in which we need to find an optimum subTree with additional constraints of a given weighted Graph arise in many real-life applications. This paper introduces the LS(Graph & Tree) framework and local search abstractions for OCT problems. These abstractions are applied to model and solve the edge weighted k-Cardinality Tree (KCT) problem. The modeling as well as experimental results show the significance of the abstractions.
Hanshellmut Nagel - One of the best experts on this subject based on the ideXlab platform.
-
behavioral knowledge representation for the understanding and creation of video sequences
Lecture Notes in Computer Science, 2003Co-Authors: Michael Arens, Hanshellmut NagelAbstract:The algorithmic generation of textual descriptions of real world image sequences requires conceptual knowledge. The algorithmic generation of synthetic image sequences from textual descriptions requires conceptual knowledge, too. An explicit representation formalism for behavioral knowledge based on formal logic is presented which can be utilized in both tasks – Understanding and Creation of video sequences. Common sense knowledge is represented at various abstraction levels in a Situation Graph Tree. This form of representation is exploited in order to fill in missing details in a natural language text describing developments for an image sequence to be synthesized.
-
representation of behavioral knowledge for planning and plan recognition in a cognitive vision system
Lecture Notes in Computer Science, 2002Co-Authors: Michael Arens, Hanshellmut NagelAbstract:The algorithmic generation of textual descriptions of image sequences requires conceptual knowledge. In our case, a stationary camera recorded image sequences of road traffic scenes. The necessary conceptual knowledge has been provided in the form of a so-called Situation Graph Tree (SGT). Other endeavors such as the generation of a synthetic image sequence from a textual description or the transformation of machine vision results for use in a driver assistance system could profit from the exploitation of the same conceptual knowledge, but more in a planning (pre-scriptive) rather than a de-scriptive context.A recently discussed planning formalism, Hierarchical Task Networks (HTNs), exhibits a number of formal similarities with SGTs. These suggest to investigate whether and to which extent SGTs may be re-cast as HTNs in order to re-use the conceptual knowledge about the behavior of vehicles in road traffic scenes for planning purposes.
