5572698
Concept exchange: constructing interoperable electronic product catalogues in an emergent environment
Research in interoperability of electronic product catalogues has primarily focused on resolving semantic conflicts arisen from the heterogeneously designed electronic product catalogues. We argue that while existing integration strategies providing static connections between various heterogeneous catalogues over mediating ontologies, ontologies themselves exhibit heterogeneity and lack of evolvability. What's more, reclassifying terms to link public ontologies is very difficult to avoid inaccuracy problem that is critical to electronic commerce. This paper highlights the problems of flexibility, exactness and evolvability that have received little attention in the literature and provides an overview of the concept exchange approach to interoperability. It illustrates why this is able to better solve the identified problems, presents the different features compared with other approaches and suggests how the concept exchange framework is working.
17686470
Inter-enterprise business document exchange
Electronic business document interoperation is the cornerstone of business process integration. An essential issue for business document interoperation is to maintain semantic consistency of the exchanged business documents between any two autonomous business communities, where the document sender and receiver have no misunderstanding in using the exchanged documents. Existing approaches to resolving this issue either adopts document standards to map heterogeneous document elements or applies business ontologies to mediate inconsistent document elements. While these approaches are effective in certain degree, the issues of limited flexibility and evolvability in using standards and the lack of accuracy in using ontologies to mediate document elements must be explored and resolved. This paper proposes a Collaborative Document Exchange (CODEX) approach to resolving the issues. In this approach, structures and concepts of business document are separated and layered in CODEX framework. Structures provide the commonality of business documents through classified concept identifiers while concepts support particularity of business documents through collaboration.
9204785
Achieving Transparent Integration of Information, Documents and Processes
While progress is made in the individual integration of business information, documents and processes, the issue of how to vertically integrate these individually integrated results needs to be resolved. This paper proposes a novel TRANSCODE approach to the issue. The approach represents business information, business documents and business processes in three TRANSCODE structures, which are then implemented, conceptualized and reified in an integrated and flexible 3-layer TRANSCODE model
37890888
Alibaba International: Building a Global Electronic Marketplace
Alibaba is the largest global electronic marketplace (GEM) in the world in terms of its participated users. It was successful due to the factors of China's foreign trade regime, the image of low product cost of China, Alibaba's contingent adaptation to users' changing requirements and e-commerce environments. Alibaba is not a technically mature GEM platform compared with the ideal functions of GEM. Suggested solution for Alibaba to continuing its success is to adopt a novel GEM connectivity model
6950256
Context representation, transformation and comparison for ad hoc product data exchange
Product data exchange is the precondition of business interoperation between Web-based firms. However, millions of small and medium sized enterprises (SMEs) encode their Web product data in ad hoc formats for electronic product catalogues. This prevents product data exchange between business partners for business interoperation. To solve this problem, this paper has proposed a novel concept-centric catalogue engineering approach for representing, transforming and comparing semantic contexts in ad hoc product data exchange. In this approach, concepts and contexts of product data are specified along data exchange chain and are mapped onto several novel XML product map (XPM) documents by utilizing XML hierarchical structure and its syntax. The designed XPM has overcome the semantic limitations of XML markup and has achieved the semantic interoperation for ad hoc product data exchange.
539228
Towards Optimally Solving the LONGEST COMMON SUBSEQUENCE Problem for Sequences with Nested Arc Annotations in Linear Time
We present exact algorithms for the NP-complete Longest Common Subsequence problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences of length at most n and nested arc structure, our algorithm determines (if existent) in time O(3.31k1+k2?n) an arc-preserving subsequence of both sequences, which can be obtained by deleting (together with corresponding arcs) k1 letters from the first and k2 letters from the second sequence. Thus, the problem is fixed-parameter tractable when parameterized by the number of deletions. This complements known approximation results which give a quadratic time factor-2-approximation for the general and polynomial time approximation schemes for restricted versions of the problem. In addition, we obtain further fixed-parameter tractability results for these restricted versions.
38762001
Pattern Matching for Arc-Annotated Sequences
A study of pattern matching for arc-annotated sequences is started. An O(nm) time algorithm is given to determine whether a length m sequence with nested arc annotations is an arc-preserving subsequence of a length n sequence with nested arc annotations, called APS(NESTED,NESTED). Arc-annotated sequences and, in particular, those with nested arc structure are motivated by applications in RNA structure comparison. Our algorithm can be used to accelerate a recent fixed-parameter algorithm for LAPCS(NESTED,NESTED) and generalizes results for ordered tree inclusion problems. In particular, the presented dynamic programming methodology implies a quadratic time algorithm for an open problem posed by Vialette.
8805498
Bounded Degree Closest k-Tree Power Is NP-Complete
An undirected graph G=V,E is the k-power of an undirected tree T=V,E' if u,v∈ E iff u andi¾?v are connected by a path of length at mosti¾?k ini¾?T. The treei¾?T is called the tree root ofi¾?G. Tree powers can be recognized in polynomial time. The thus naturally arising question is whether a graphi¾?G can be modified by adding or deleting a specified number of edges such thati¾?G becomes a tree power. This problem becomes NP-complete for ki¾? 2. Strengthening this result, we answer the main open question of Tsukiji and Chen [COCOON 2004] by showing that the problem remains NP-complete when additionally demanding that the tree roots must have bounded degree.
6234679
A Model-based Approach to Hair Region Segmentation
Hair regions represent an important external feature in many tasks involving the processing of human faces. Currently, the task of locating the hair region in a facial image requires manual intervention. In this paper we examine the different aspects of the hair region segmentation problem and develop an automatic system for such a problem. The system incorporates the human knowledge on where the hair is usually located in a facial image. Segmentation is performed via the classification of image pixels and is based on both textural and geometrical features. Experiments have shown that the segmentation results are generally satisfactory and are at least comparable to the performance of manual extraction.
10069776
Automated Generation of Search Tree Algorithms for Hard Graph
Modification Problems
Abstract
We present a framework for an automated 
generation of exact search tree algorithms for NP-hard problems.
The purpose of our approach is twofold—rapid development and 
improved upper bounds. 
Many search tree algorithms for various problems
in the literature are based on complicated
case distinctions. Our approach may lead to a much 
simpler process of developing and analyzing these algorithms.
Moreover, using the sheer computing power of machines it may also 
lead to improved upper bounds on
search tree sizes (i.e., faster exact solving algorithms) in comparison
with previously developed “hand-made” search trees.
Among others, such an example is given with the NP-complete 
Cluster Editing problem (also known as Correlation
Clustering on complete unweighted graphs), which asks for the minimum
number of edge additions and deletions to create a graph which is a
disjoint union of cliques. The
hand-made search tree
for Cluster Editing
had worst-case size O(2.27k), which now is improved to 
O(1.92k) due to our new method.
(Herein, k denotes the number of edge modifications allowed.)

