Canonical decomposition for bipartite graphs, which was introduced by Fouquet, Giakoumakis, and Vanherpe (1999), is a decomposition scheme for bipartite graphs associated with modular decomposition. Weak-bisplit graphs are bipartite graphs totally decomposable (i.e., reducible to single vertices) by canonical decomposition. Canonical decomposition comprises series, parallel, and K+S decomposition. This paper studies a decomposition scheme comprising only parallel and K+S decomposition. We show that bipartite graphs totally decomposable by this decomposition are precisely P6-free chordal bipartite graphs. This characterization indicates that P6-free chordal bipartite graphs can be recognized in linear time using the recognition algorithm for weak-bisplit graphs presented by Giakoumakis and Vanherpe (2003).

Early reviews, posted on online review sites shortly after products enter the market, are useful for estimating long-term evaluations of those products and making decisions. However, such reviews can be influenced easily by anomalous reviewers, including malicious and fraudulent reviewers, because the number of early reviews is usually small. It is therefore challenging to detect anomalous reviewers from early reviews and estimate long-term evaluations by reducing their influences. We find that two characteristics of heterogeneity on actual review sites such as Amazon.com cause difficulty in detecting anomalous reviewers from early reviews. We propose ideas for consideration of heterogeneity, and a methodology for computing reviewers' degree of anomaly and estimating long-term evaluations simultaneously. Our experimental evaluations with actual reviews from Amazon.com revealed that our proposed method achieves the best performance in 19 of 20 tests compared to state-of-the-art methodologies.

Detecting signals in a very large multiple-input multiple-output (MIMO) system requires high complexy of implementation. Thus, belief propagation based detection has been studied recently because of its low complexity. When the transmitted signal sequence is encoded using a channel code decodable by a factor-graph-based algorithm, MIMO signal detection and channel decoding can be combined in a single factor graph. In this paper, a low density parity check (LDPC) coded MIMO system is considered, and two types of factor graphs: bipartite and tripartite graphs are compared. The former updates the log-likelihood-ratio (LLR) values at MIMO detection and parity checking simultaneously. On the other hand, the latter performs the updates alternatively. Simulation results show that the tripartite graph achieves faster convergence and slightly better bit error rate performance. In addition, it is confirmed that the LLR damping in LDPC decoding is important for a stable convergence.

Web search queries are usually vague, ambiguous, or tend to have multiple intents. Users have different search intents while issuing the same query. Understanding the intents through mining subtopics underlying a query has gained much interest in recent years. Query suggestions provided by search engines hold some intents of the original query, however, suggested queries are often noisy and contain a group of alternative queries with similar meaning. Therefore, identifying the subtopics covering possible intents behind a query is a formidable task. Moreover, both the query and subtopics are short in length, it is challenging to estimate the similarity between a pair of short texts and rank them accordingly. In this paper, we propose a method for mining and ranking subtopics where we introduce multiple semantic and content-aware features, a bipartite graph-based ranking (BGR) method, and a similarity function for short texts. Given a query, we aggregate the suggested queries from search engines as candidate subtopics and estimate the relevance of them with the given query based on word embedding and content-aware features by modeling a bipartite graph. To estimate the similarity between two short texts, we propose a Jensen-Shannon divergence based similarity function through the probability distributions of the terms in the top retrieved documents from a search engine. A diversified ranked list of subtopics covering possible intents of a query is assembled by balancing the relevance and novelty. We experimented and evaluated our method on the NTCIR-10 INTENT-2 and NTCIR-12 IMINE-2 subtopic mining test collections. Our proposed method outperforms the baselines, known related methods, and the official participants of the INTENT-2 and IMINE-2 competitions.

Suppose one of the edges is attacked in a graph G, where some number of guards are placed on some of its vertices. If a guard is placed on one of the end-vertices of the attacked edge, she can defend such an attack to protect G by passing over the edge. For each of such attacks, every guard is allowed either to move to a neighboring vertex, or to stay at where she is. The eternal vertex cover number τ∞(G) is the minimum number of guards sufficient to protect G from any length of any sequence of edge attacks. This paper derives the eternal vertex cover number τ∞(G) of such graphs constructed by replacing each edge of a tree by an arbitrary elementary bipartite graph (or by an arbitrary clique), in terms of easily computable graph invariants only, thereby showing that τ∞(G) can be computed in polynomial time for such graphs G.

In this paper, we propose a novel ranking method called VisualTextualRank which ranks media data according to the relevance between the data and specified keywords. We apply our method to the system of video shot ranking which aims to automatically obtain video shots corresponding to given action keywords from Web videos. The keywords can be any type of action such as “surfing wave” (sport action) or “brushing teeth” (daily activity). Top ranked video shots are expected to be relevant to the keywords. While our baseline exploits only visual features of the data, the proposed method employs both textual information (tags) and visual features. Our method is based on random walks over a bipartite graph to integrate visual information of video shots and tag information of Web videos effectively. Note that instead of treating the textual information as an additional feature for shot ranking, we explore the mutual reinforcement between shots and textual information of their corresponding videos to improve shot ranking. We validated our framework on a database which was used by the baseline. Experiments showed that our proposed ranking method, VisualTextualRank, improved significantly the performance of the system of video shot extraction over the baseline.

Complex-valued Hopfield associative memory (CHAM) is one of the most promising neural network models to deal with multilevel information. CHAM has an inherent property of rotational invariance. Rotational invariance is a factor that reduces a network's robustness to noise, which is a critical problem. Here, we proposed complex-valued bipartite auto-associative memory (CBAAM) to solve this reduction in noise robustness. CBAAM consists of two layers, a visible complex-valued layer and an invisible real-valued layer. The invisible real-valued layer prevents rotational invariance and the resulting reduction in noise robustness. In addition, CBAAM has high parallelism, unlike CHAM. By computer simulations, we show that CBAAM is superior to CHAM in noise robustness. The noise robustness of CHAM decreased as the resolution factor increased. On the other hand, CBAAM provided high noise robustness independent of the resolution factor.

A (k,2)-track layout of a graph G consists of a 2-track assignment of G and an edge k-coloring of G with no monochromatic X-crossing. This paper studies the problem of (k,2)-track layout of bipartite graph subdivisions. Recently V. Dujmovi and D.R. Wood showed that for every integer d ≥ 2, every graph G with n vertices has a (d+1,2)-track layout of a subdivision of G with 4 log d qn(G) +3 division vertices per edge, where qn(G) is the queue number of G. This paper improves their result for the case of bipartite graphs, and shows that for every integer d ≥ 2, every bipartite graph Gm,n has a (d+1,2)-track layout of a subdivision of Gm,n with 2 log d n -1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n with m ≥ n.

This paper deals with a universal coding problem for a certain kind of multiterminal source coding system that we call the complementary delivery coding system. In this system, messages from two correlated sources are jointly encoded, and each decoder has access to one of the two messages to enable it to reproduce the other message. Both fixed-to-fixed length and fixed-to-variable length lossless coding schemes are considered. Explicit constructions of universal codes and bounds of the error probabilities are clarified via type-theoretical and graph-theoretical analyses.

For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmovi and D. R. Wood showed that for every integer d ≥ 2, every graph G has a d-queue layout of a subdivision of G with 2logd qn(G)+1 division vertices per edge, where qn(G) is the queue number of G. This paper improves the result for the case of a bipartite graph, and shows that for every integer d ≥ 2, every bipartite graph Gm,n has a d-queue layout of a subdivision of Gm,n with logd n-1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n (m ≥ n).

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine logd n times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph Gn1,n2 having two partite sets with n1 and n2 vertices respectively (n1 ≥ n2) in which each edge crosses the spine logd n2 -1 times.

We present a simple decoding algorithm that modifies soft bit-flipping algorithm for decoding LDPC codes. In our method, a new parameter is explored to distinguish the variables (symbols) belonging to the same number of unsatisfied constraints. A token is also assigned in the method to avoid repeated flipping of the same variable, rather than using a constant taboo length. Our scheme shows a similar computational load as the taboo-based algorithm, while having a similar decoding performance as the belief propagation algorithm.

Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

Let G = (A, B, E) be a bipartite graph with bipartition (A:B) of vertex set and edge set E. For each vertex v, Γ(v) denotes the set of adjacent vertices to v. G is said to be t-convex on the vertex set A if there is a tree and a one-to-one correspondence between vertices in A and edges of the tree such that for each vertex b B the edges of the tree corresponding to vertices in Γ(b) form a path on the tree. G is doubly t-convex if it is convex both on vertex set A and on B. In this paper, we show that, the class of doubly t-convex graphs is exactly the class of bipartite circle graphs.

Throughout the paper, the proper operating of the self-routing principle in 2-D shuffle multistage interconnection networks (MINs) is analysed. (The notation 1-D MIN and 2-D MIN is applied for a MIN which interconnects 1-D and 2-D data, respectively.) Two different methods for self-routing in 2-D shuffle MINs are presented: (1) The application of self-routing in 1-D MINs by a switch-pattern preserving transformation of 1-D shuffle stages into 2-D shuffle stages (and vice versa) and (2) the general concept of self-routing in 2-D shuffle MINs based on self-routing with regard to each coordinate which is the original contribution of the paper. Several examples are provided which make the various problems transparent.

As a first step to develop a system to analyze or recognize patterns contained in mages, it is important to provide a good base representation that can facilitate efficiently the interpretation of such patterns. Since structural features of basic patterns in document images such as characters or tables are horizontal and vertical stroke components, we propose a new expression of document image based on the MCR expression that can express well such features of text and tabular components of an image.

Throughout the paper, the nearest-neighbour (NN) interconnection of switches within a multistage interconnection network (MIN) is analysed. Three main results are obtained: (1) The switch preserving transformation of a 2-D MIN into the 1-D MIN (and vice versa) (2) The rearrangeability of the MIN and (3) The number of stages (NS) for the rearrangeable nonblocking interconnection. The analysis is extended to any dimension of the interconnected data set. The topological equivalence between 1-D MINs with NN interconnections (NN-MINs) and 1-D cellular arrays is shown.

The Minimum Covering Run (MCR) expression used for representing binary images has been proposed [1]-[3]. The MCR expression is an adaptation from horizontal and vertical run expression. In the expression, some horizontal and vertical runs are used together for representing binary images in which total number of them is minimized. It was shown that, sets of horizontal and vertical runs representing any binary image could be viewed as partite sets of a bipartite graph, then the MCR expression of binary images was found analogously by constructing a maximum matching as well as a minimum covering in the corresponding graph. In the original algorithm, the most efficient algorithm, proposed by Hopcroft, solving the graph-theoretical problems mentioned above, associated with the Rectangular Segment Analysis (RSA) was used for finding the MCR expression. However, the original algorithm still suffers from a long processing time. In this paper, we propose two new efficient MCR algorithms that are beneficial to a practical implementation. The new algorithms are composed of two main procedures; i.e., Partial Segment Analysis (PSA) and construction of a maximum matching. It is shown in this paper that the first procedure which is directly an improvement to the RSA, appoints well a lot of representative runs of the MCR expression in regions of text and line drawing. Due to the PSA, the new algorithms reduce the number of runs used in the technique of solving the matching problem in corresponding graphs so that satisfactory processing time can be obtained. To clarify the validity of new algorithms proposed in this paper, the experimental results show the comparative performance of the original and new algorithms in terms of processing time.

An efficient technique for expressing document image is required as part of a unified approach to document image processing. This paper presents a new method, Minimum Covering Run (MCR), for expressing binary images. The name being adapted from horizontal or vertical run representation. The proposed technique uses some horizontal and vertical runs together to represent binary images in which the total number of representative runs is minimized. Considering the characteristic of above run types precisely, it is shown that horizontal and vertical runs of any binary image could be thought of as partite sets of a bipartite graph. Consequently, the MCR expression that corresponds to the construction of one of the most interesting problems in graphs; i.e., maximum matching, is analogously found by using an algorithm which solves this problem in a corresponding graph. The most efficient algorithm takes at most O(n5/2) computations for solving the problem where n is the sum of cardinalities of both partite sets. However, some patterns in images like tables or line drowings, generally, have a large number of runs representing them which results in a long processing time. Therefore, we provide the Rectangular Segment Analysis (RSA) as a pre-processing to define runs representing such patterns beforehand. We also show that horizontal and vertical covering parts of the proposed expression are able to represent stroke components of characters in document images. As an implementation, an efficient algorithm including arrangement for run data structure of the MCR expression is presented. The experimental results show the possibility of stroke extraction of characters in document images. As an application, some patterns such as tables can be extracted from document images.