295 results on '"bipartite graphs"'
Search Results
2. Crossing Minimization in Weighted Bipartite Graphs
- Author
-
Cesim Erten, Omer Karatas, Melih Sözdinler, Olca A. Çakiroğlu, Işık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Işık University, Faculty of Engineering, Department of Computer Engineering, Çakıroğlu, Olca Arda, Erten, Cesim, Karataş, Ömer, and Sözdinler, Melih more...
- Subjects
Combinatorial optimization ,02 engineering and technology ,Complete bipartite graph ,Polynomials ,01 natural sciences ,law.invention ,Approximation ratio ,law ,Graph drawing ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Polynomial-time algorithms ,Mathematics ,Bipartite graph ,Problem solving ,Graph Layout ,Crossing minimization ,Approximation algorithm ,Approximation algorithms ,Planarity testing ,Computational complexity ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Graph layout ,020201 artificial intelligence & image processing ,Crossing number (graph theory) ,Assignment problem ,Optimization ,Polynomial approximation ,0102 computer and information sciences ,NP Complete ,Theoretical Computer Science ,Combinatorics ,Approximation ratios ,Weighted bipartite graphs ,Line graph ,Clique-width ,Unweighted graph ,Weight balance ,Heuristic algorithms ,Planarity ,Nonnegative weights ,Bipartite graphs ,Discrete mathematics ,Crossings (pipe and cable) ,Edge density ,Unweighted case ,Graph theory ,Independent set ,Drawings ,Heuristic methods ,Heuristics - Abstract
Given a bipartite graph G = (L-0, L-1, E) and a fixed ordering of the nodes in L-0, the problem of finding an ordering of the nodes in L-1 that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances. Partially supported by TUBITAK-The Scientific and Technological Research Council of Turkey, grant 106E071 Publisher's Version Q4 WOS:000247069500010 more...
- Published
- 2007
- Full Text
- View/download PDF
Catalog
3. Movies Recommendation Networks as Bipartite Graphs
- Author
-
Jelena Grujić, Informatics and Applied Informatics, and Computational Modelling
- Subjects
topology ,bipartite graphs ,business.industry ,Value (computer science) ,Topology (electrical circuits) ,Complex network ,Filter (higher-order function) ,computer.software_genre ,Data set ,recommendation networks ,Bipartite graph ,The Internet ,Data mining ,business ,computer ,Mathematics ,Network model - Abstract
In this paper we investigate the users' recommendation networks based on the large data set from the Internet Movie Database. We study networks based on two types of inputs: first (monopartite) generated directly from the recommendation lists on the website, and second (bipartite) generated through the users' habits. Using a threshold number of votes per movie to filter the data, we actually introduce a control parameter, and then by tuning this parameter we study its effect on the network structure. From the detailed analysis of both networks we find that certain robust topological features occur independently from the value of the control parameter. We also present a comparison of the network clustering and shortest paths on the graphs with a randomized network model based on the same data. more...
- Published
- 2008
- Full Text
- View/download PDF
4. Sequences of Radius k for Complete Bipartite Graphs
- Author
-
Paweł RząźEwski, Zbigniew Lonc, and Michał DăźBski
- Subjects
020206 networking & telecommunications ,010103 numerical & computational mathematics ,02 engineering and technology ,01 natural sciences ,Complete bipartite graph ,Pseudorandom binary sequence ,Upper and lower bounds ,Graph ,Combinatorics ,0202 electrical engineering, electronic engineering, information engineering ,Bipartite graph ,0101 mathematics ,External database ,Mathematics - Abstract
Let G be a graph. A k-radius sequence forG is a sequence of vertices of G such that for every edge uv of G vertices u and v appear at least once within distance k in the sequence. The length of a shortest k-radius sequence for G is denoted by $$f_kG$$. Such sequences appear in a problem related to computing values of some 2-argument functions. Suppose we have a set V of large objects, stored in an external database, and our cache can accommodate at most $$k+1$$ objects from V at one time. If we are given a set E of pairs of objects for which we want to compute the value of some 2-argument function, and assume that our cache is managed in FIFO manner, then $$f_kG$$ where $$G=V,E$$ is the minimum number of times we need to copy an object from the database to the cache. We give an asymptotically tight estimation on $$f_kG$$ for complete bipartite graphs. We show that for every $$\epsilon >0$$ we have $$f_kK_{m,n}\le 1+\epsilon d_k\frac{mn}{k}$$, provided that both m and n are sufficiently large --- where $$d_k$$ depends only on k. This upper bound asymptotically coincides with the lower bound $$f_kG\ge d_k\frac{eG}{k}$$, valid for all bipartite graphs. We also show that determining $$f_kG$$ for an arbitrary graph G is NP-hard for every constant $$k>1$$. more...
- Published
- 2016
- Full Text
- View/download PDF
5. Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs
- Author
-
Kenjiro Takazawa
- Subjects
Discrete mathematics ,021103 operations research ,Matching (graph theory) ,0211 other engineering and technologies ,Dulmage–Mendelsohn decomposition ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Complete bipartite graph ,Modular decomposition ,Combinatorics ,010201 computation theory & mathematics ,Set function ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,3-dimensional matching ,Bipartite graph ,Blossom algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
A square-free 2-matching in an undirected graph is a simple 2-matching without cycles of length four. In bipartite graphs, the maximum square-free 2-matching problem is well-solved. Previous results include min-max theorems, polynomial combinatorial algorithms, polyhedral description with dual integrality, and discrete convex structure. In this paper, we further investigate the structure of square-free 2-matchings in bipartite graphs to present new decomposition theorems, which serve as an analogue of the Dulmage-Mendelsohn decomposition for bipartite matchings and the Edmonds-Gallai decomposition for nonbipartite matchings. We exhibit two canonical minimizers of the set function in the min-max formula, and a characterization of the maximum square-free 2-matchings with the aid of these canonical minimizers. more...
- Published
- 2016
- Full Text
- View/download PDF
6. A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs
- Author
-
Vangelis Th. Paschos, Édouard Bonnet, Bruno Escoffier, and Georgios Stamoulis
- Subjects
Matching (graph theory) ,Vertex cover ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,Combinatorial algorithms ,01 natural sciences ,Combinatorics ,010201 computation theory & mathematics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Bounded function ,0202 electrical engineering, electronic engineering, information engineering ,Bipartite graph ,Cover (algebra) ,Time complexity ,MathematicsofComputing_DISCRETEMATHEMATICS ,Hopcroft–Karp algorithm ,Mathematics - Abstract
We study the polynomial time approximation of the max k-vertex cover problem in bipartite graphs and propose a purely combinatorial algorithm that beats the only such known algorithm, namely the greedy approach. We present a computer-assisted analysis of our algorithm, establishing that the worst case approximation guarantee is bounded below by 0.821. more...
- Published
- 2016
- Full Text
- View/download PDF
7. Fully Dynamic Matching in Bipartite Graphs
- Author
-
Aaron Bernstein and Cliff Stein
- Subjects
Combinatorics ,Discrete mathematics ,Cardinality ,Matching (graph theory) ,Deterministic algorithm ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Arboricity ,Vertex cover ,Bipartite graph ,Binary logarithm ,Constant (mathematics) ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
We present two fully dynamic algorithms for maximum cardinality matching in bipartite graphs. Our main result is a deterministic algorithm that maintains a \((3/2 + \epsilon )\) approximation in worst-case update time \(O(m^{1/4}\epsilon ^{-2.5})\). This algorithm is polynomially faster than all previous deterministic algorithms for any constant approximation, and faster than all previous algorithms (randomized included) that achieve a better-than-2 approximation. We also give stronger results for bipartite graphs whose arboricity is at most \(\alpha \), achieving a \((1+ \epsilon )\) approximation in worst-case update time \(O(\alpha (\alpha + \log (n)) + \epsilon ^{-4}(\alpha + \log (n)) + \epsilon ^{-6})\), which is \(O(\alpha (\alpha + \log n))\) for constant \(\epsilon \). Previous results for small arboricity graphs had similar update times but could only maintain a maximal matching (2-approximation). All these previous algorithms, however, were not limited to bipartite graphs. more...
- Published
- 2015
- Full Text
- View/download PDF
8. Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
- Author
-
Tian Liu, Min Lu, and Ke Xu
- Subjects
Combinatorics ,Indifference graph ,Dense graph ,Computer Science::Discrete Mathematics ,Dominating set ,Chordal graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Bipartite graph ,Strong perfect graph theorem ,Maximal independent set ,Complete bipartite graph ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
An independent dominating set in a graph is a subset of vertices, such that no edge has both ends in the subset, and each vertex either itself is in the subset or has a neighbor in the subset. In a convex bipartite (circular convex bipartite, triad convex bipartite, respectively) graph, there is a linear ordering (a circular ordering, a triad, respectively) defined on one class of vertices, such that for every vertex in the other class, the neighborhood of this vertex is an interval (a circular arc, a subtree, respectively), where a triad is three paths with a common end. The problem of finding a minimum independent dominating set, called independent domination, is known \(\mathcal{NP}\)-complete for bipartite graphs and tractable for convex bipartite graphs. In this paper, we make polynomial time reductions for independent domination from triad- and circular-convex bipartite graphs to convex bipartite graphs. more...
- Published
- 2013
- Full Text
- View/download PDF
9. Fast Dynamic Weight Matchings in Convex Bipartite Graphs
- Author
-
Quan Zu, Bin Yu, and Miaomiao Zhang
- Subjects
Combinatorics ,Discrete mathematics ,Amortized analysis ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Regular polygon ,Bipartite graph ,Convex bipartite graph ,Maximum weight matching ,Complete bipartite graph ,Blossom algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics ,Vertex (geometry) - Abstract
This paper considers the problem of maintaining a maximum weight matching in a dynamic vertex weighted convex bipartite graph \({G=(X,Y,E)}\), in which the neighbors of each \({x\in X}\) form an interval of \({Y}\) where Y is linearly ordered, and each vertex has an associated weight. The graph is subject to insertions and deletions of vertices and edges. Our algorithm supports the update operations in \({O(\log ^2{|V|})}\) amortized time, obtains the matching status of a vertex (whether it is matched) in constant worst-case time, and finds the mate of a matched vertex (with which it is matched) in polylogarithmic worst-case time. Our solution is more efficient than the best known solution for the problem in the unweighted version. more...
- Published
- 2015
- Full Text
- View/download PDF
10. Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract)
- Author
-
Tian Liu, Zhao Lu, and Ke Xu
- Subjects
Pure mathematics ,Mathematics::Combinatorics ,Regular polygon ,TheoryofComputation_GENERAL ,Convex bipartite graph ,Connected domination ,Complete bipartite graph ,Connected dominating set ,Combinatorics ,Computer Science::Discrete Mathematics ,Chordal graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Bipartite graph ,Time complexity ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Finding a minimum connected dominating set (connected domination) is known \(\cal{NP}\)-complete for chordal bipartite graphs, but tractable for convex bipartite graphs. In this paper, connected domination is shown tractable for circular- and triad-convex bipartite graphs, by efficient reductions from these graphs to convex bipartite graphs. more...
- Published
- 2013
- Full Text
- View/download PDF
11. Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Author
-
Ke Xu, Wei Jiang, Chaoyi Wang, and Tian Liu
- Subjects
Discrete mathematics ,Mathematics::Combinatorics ,Vertex cover ,Complete bipartite graph ,Vertex (geometry) ,Combinatorics ,Tree (data structure) ,Computer Science::Discrete Mathematics ,Chordal graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Bipartite graph ,Maximal independent set ,Feedback vertex set ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
A feedback vertex set in a graph is a subset of vertices, such that the complement of this subset induces a forest. Finding a minimum feedback vertex set (FVS) is \(\cal{NP}\)-complete on bipartite graphs, but tractable on chordal bipartite graphs. A bipartite graph is called tree convex, if a tree is defined on one part of the vertices, such that for every vertex in the other part, the neighborhood of this vertex induces a subtree. First, we show that chordal bipartite graphs form a proper subset of tree convex bipartite graphs. Second, we show that FVS is \(\cal{NP}\)-complete on the tree convex bipartite graphs where the sum of the degrees of vertices whose degree is at least three on the tree is unbounded. Combined with known tractability where this sum is bounded, we show a dichotomy of complexity of FVS on tree convex bipartite graphs. more...
- Published
- 2012
- Full Text
- View/download PDF
12. Independent Domination on Tree Convex Bipartite Graphs
- Author
-
Ke Xu, Yu Song, and Tian Liu
- Subjects
Discrete mathematics ,Convex bipartite graph ,Tree-depth ,Complete bipartite graph ,Combinatorics ,Computer Science::Discrete Mathematics ,Dominating set ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Independent set ,Bipartite graph ,Cograph ,Maximal independent set ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
An independent dominating set in a graph is a subset of vertices, such that every vertex outside this subset has a neighbor in this subset (dominating), and the induced subgraph of this subset contains no edge (independent). It was known that finding the minimum independent dominating set (Independent Domination) is $\cal{NP}$ -complete on bipartite graphs, but tractable on convex bipartite graphs. A bipartite graph is called tree convex, if there is a tree defined on one part of the vertices, such that for every vertex in another part, the neighborhood of this vertex is a connected subtree. A convex bipartite graph is just a tree convex one where the tree is a path. We find that the sum of larger-than-two degrees of the tree is a key quantity to classify the computational complexity of independent domination on tree convex bipartite graphs. That is, when the sum is bounded by a constant, the problem is tractable, but when the sum is unbounded, and even when the maximum degree of the tree is bounded, the problem is $\cal{NP}$ -complete. more...
- Published
- 2012
- Full Text
- View/download PDF
13. Bandwidth of Convex Bipartite Graphs and Related Graphs
- Author
-
Anish Man Singh Shrestha, Satoshi Tayu, and Shuichi Ueno
- Subjects
Discrete mathematics ,Mathematics::Combinatorics ,Matching (graph theory) ,TheoryofComputation_GENERAL ,Complete bipartite graph ,Computer Science Applications ,Theoretical Computer Science ,Metric dimension ,Combinatorics ,Indifference graph ,Pathwidth ,Computer Science::Discrete Mathematics ,Chordal graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Signal Processing ,Bipartite graph ,Permutation graph ,Maximal independent set ,Information Systems ,Hopcroft–Karp algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
It is known that the bandwidth problem is NP-complete for chordal bipartite graphs, while the problem can be solved in polynomial time for bipartite permutation graphs, which is a subclass of chordal bipartite graphs. This paper shows that the problem is NP-complete even for convex bipartite graphs, a subclass of chordal bipartite graphs and a superclass of bipartite permutation graphs. We provide an O(n)-time, 4-approximation algorithm and an O(n log2 n)-time, 2-approximation algorithm for convex bipartite graphs with n vertices. For 2-directional orthogonal ray graphs, which is a subclass of chordal bipartite graphs and a superclass of convex bipartite graphs, we provide an O(n2 log n)-time, 3-approximation algorithm, where n is the number of vertices. more...
- Published
- 2011
- Full Text
- View/download PDF
14. Bipartite Graphs and Coverings
- Author
-
William Zhu, Fan Min, and Shiping Wang
- Subjects
Discrete mathematics ,Combinatorics ,Matching (graph theory) ,Covering graph ,Independent set ,Index set ,Bipartite graph ,Maximal independent set ,Rough set ,Complete bipartite graph ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
In many real world applications, data are organized by coverings, instead of partitions. Covering-based rough sets have been proposed to cope with this type of data. Covering-based rough set theory is more general than rough set theory, then there is a need to employ sophisticated theories to make it more adaptive to applications. Covering is one of core concepts in covering-based rough sets, and it is urgent to connect coverings with other data models. This paper establishes the relationship between coverings and bipartite graphs. Through its index set, a covering induces some isomorphic bipartite graphs. Conversely, a bipartite graph induces a covering of the set of vertices. These inductions are converse with each other. more...
- Published
- 2011
- Full Text
- View/download PDF
15. Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
- Author
-
Federico Mancini, Pinar Heggernes, R. Sritharan, and Charis Papadopoulos
- Subjects
Combinatorics ,Discrete mathematics ,Treewidth ,Indifference graph ,Mathematics::Combinatorics ,Pathwidth ,Lexicographic breadth-first search ,Computer Science::Discrete Mathematics ,Chordal graph ,Interval graph ,Split graph ,Tree-depth ,Mathematics - Abstract
A graph class is sandwich monotone if, for every pair of its graphs G 1 = (V ,E 1 ) and G 2 = (V ,E 2 ) with E 1 *** E 2 , there is an ordering e 1 , ..., e k of the edges in E 2 *** E 1 such that G = (V , E 1 *** {e 1 , ..., e i }) belongs to the class for every i between 1 and k . In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono from 1997. So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently. more...
- Published
- 2009
- Full Text
- View/download PDF
16. A Note on n-Critical Bipartite Graphs and Its Application
- Author
-
Zhe Nie and Yueping Li
- Subjects
Discrete mathematics ,Mathematics::Combinatorics ,Strong perfect graph theorem ,Complete bipartite graph ,Combinatorics ,Indifference graph ,Pathwidth ,Computer Science::Discrete Mathematics ,Chordal graph ,Bipartite graph ,Cograph ,Maximal independent set ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
In matching theory, n -critical graphs play an important role in the decomposition of graphs with respect to perfect matchings. Since bipartite graphs cannot be n -critical when n > 0, we amend the classical definition of n -critical graphs and propose the concept of n -critical bipartite graphs. Let G = (B ,W ; E ) be a bipartite graph with n = |W | *** |B |, where B and W are the bipartitions of vertex set, E is the edge set. Then, G is n -critical if when deleting any n distinct vertices of W , the remaining subgraph of G has a perfect matching. Furthermore, an algorithm for determining n -critical bipartite graphs is given which runs in O (|W ||E |) time, in the worst case. Our work helps to design a job assignment circuit which has high robustness. more...
- Published
- 2009
- Full Text
- View/download PDF
17. Constrained Matching Problems in Bipartite Graphs
- Author
-
Monaldo Mastrolilli and Georgios Stamoulis
- Subjects
Discrete mathematics ,Combinatorics ,Matching (graph theory) ,Linear programming ,Generalization ,3-dimensional matching ,Bipartite graph ,Approximation algorithm ,Complete bipartite graph ,Blossom algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
We study the following generalization of maximum matchings in bipartite graphs: given a bipartite graph such that each edge has a unique color cj, we are asked to find a maximum matching that has no more than wj edges of color cj. We study bi-criteria approximation algorithms for this problem based on linear programming techniques and we show how we can obtain a family of algorithms with varying performance guarantees that can violate the color bounds. Our problem is motivated from network problems in optical fiber technologies. more...
- Published
- 2012
- Full Text
- View/download PDF
18. Partitioning Signed Bipartite Graphs for Classification of Individuals and Organizations
- Author
-
Sujogya Banerjee, Arunabha Sen, Sedat Gokalp, Hasan Davulcu, and Kaushik Sarkar
- Subjects
Theoretical computer science ,Bipartite graph ,Disjoint sets ,Data mining ,Cluster analysis ,computer.software_genre ,computer ,Mathematics - Abstract
In this paper, we use signed bipartite graphs to model opinions expressed by one type of entities (e.g., individuals, organizations) about another (e.g., political issues, religious beliefs), and based on the strength of that opinion, partition both types of entities into two clusters. The clustering is done in such a way that support for the second type of entity by the first within a cluster is high and across the cluster is low. We develop an automated partitioning tool that can be used to classify individuals and/or organizations into two disjoint groups based on their beliefs, practices and expressed opinions. more...
- Published
- 2012
- Full Text
- View/download PDF
19. Privacy Preserving Social Network Publication on Bipartite Graphs
- Author
-
Lei Wang, Jiwu Jing, Ji Xiang, and Jian Zhou
- Subjects
Theoretical computer science ,Social network ,Computer science ,business.industry ,Generalization ,Data publishing ,computer.software_genre ,Partition (database) ,Privacy preserving ,Bipartite graph ,Data mining ,business ,computer ,Computer Science::Databases ,Computer Science::Cryptography and Security - Abstract
In social networks, some data may come in the form of bipartite graphs, where properties of nodes are public while the associations between two nodes are private and should be protected. When publishing the above data, in order to protect privacy, we propose to adopt the idea generalizing the graphs to super-nodes and super-edges. We investigate the problem of how to preserve utility as much as possible and propose an approach to partition the nodes in the process of generalization. Our approach can give privacy guarantees against both static attacks and dynamic attacks, and at the same time effectively answer aggregate queries on published data. more...
- Published
- 2012
- Full Text
- View/download PDF
20. Computing Maximum Non-crossing Matching in Convex Bipartite Graphs
- Author
-
Xiaomin Liu, Danny Z. Chen, and Haitao Wang
- Subjects
Discrete mathematics ,Factor-critical graph ,Matching (graph theory) ,Convex bipartite graph ,Complete bipartite graph ,Combinatorics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,3-dimensional matching ,Bipartite graph ,Computer Science::Data Structures and Algorithms ,Blossom algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Hopcroft–Karp algorithm ,Mathematics - Abstract
We consider computing a maximum non-crossing matching in convex bipartite graphs. For a convex bipartite graph of n vertices and m edges, we present an O (n logn ) time algorithm for finding a maximum non-crossing matching in the graph. The previous best algorithm for this problem takes O (m +n logn ) time. Since m =Θ(n 2) in the worst case, our result improves the previous solution for large m . more...
- Published
- 2012
- Full Text
- View/download PDF
21. Readable Representations for Large-Scale Bipartite Graphs
- Author
-
Jiro Tanaka, Kazuo Misue, and Shuji Sato
- Subjects
Modular decomposition ,Information visualization ,Theoretical computer science ,business.industry ,Graph drawing ,Computer science ,Bipartite graph ,Force-directed graph drawing ,User interface ,Cluster analysis ,business ,Graph - Abstract
Bipartite graphs appear in various scenes in the real world, and visualizing these graphs helps improve our understanding of network structures. The amount of information that is available to us has increased dramatically in recent years, and it is therefore necessary to develop a drawing technique that corresponds to large-scale graphs. In this paper, we describe drawing methods to make large-scale bipartite graphs easy to read. We propose two techniques: "node contraction drawing," which involves collecting similar nodes and drawing them as one node, and "isosimilarity contour drawing," which puts clusters into an outlined area. We developed interactive user interfaces for the drawing methods and conducted an evaluation experiment to demonstrate the effectiveness of the proposed techniques. more...
- Published
- 2008
- Full Text
- View/download PDF
22. Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- Author
-
Marc Demange and Tınaz Ekim
- Subjects
Discrete mathematics ,Combinatorics ,Indifference graph ,Pathwidth ,Computer Science::Discrete Mathematics ,Chordal graph ,Bipartite graph ,Cograph ,Maximal independent set ,Complete bipartite graph ,1-planar graph ,Mathematics - Abstract
Yannakakis and Gavril showed in [10] that the problem of finding a maximal matching of minimum size (MMM for short), also called Minimum Edge Dominating Set, is NP-hard in bipartite graphs of maximum degree 3 or planar graphs of maximum degree 3. Horton and Kilakos extended this result to planar bipartite graphs and planar cubic graphs [6]. Here, we extend the result of Yannakakis and Gavril in [10] by showing that MMM is NP-hard in the class of k-regular bipartite graphs for all k ≥ 3 fixed. more...
- Published
- 2008
- Full Text
- View/download PDF
23. Gathering Asynchronous Oblivious Agents with Local Vision in Regular Bipartite Graphs
- Author
-
Samuel Guilbault and Andrzej Pelc
- Subjects
Computer Science::Multiagent Systems ,Theoretical computer science ,Asynchronous communication ,Existential quantification ,Bipartite graph ,Snapshot (computer storage) ,Mobile agent ,Regular graph ,Graph ,Mathematics - Abstract
We consider the problem of gathering identical, memoryless, mobile agents in one node of an anonymous graph. Agents start from different nodes of the graph. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, an agent takes a snapshot of its immediate neighborhood (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each agent. The novelty of our model with respect to the existing literature on gathering asynchronous oblivious agents in graphs is that the agents have very restricted perception capabilities: they can only see their immediate neighborhood. An initial configuration of agents is called gatherable if there exists an algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) The gathering problem is to determine which configurations are gatherable and find a (universal) algorithm which gathers all gatherable configurations. We give a complete solution of the gathering problem for regular bipartite graphs. Our main contribution is the proof that the class of gatherable initial configurations is very small: it consists only of "stars" (an agent A with all other agents adjacent to it) of size at least 3. On the positive side we give an algorithm accomplishing gathering for every gatherable configuration. more...
- Published
- 2011
- Full Text
- View/download PDF
24. The P k Partition Problem and Related Problems in Bipartite Graphs
- Author
-
Jérôme Monnot and Sophie Toulouse
- Subjects
Discrete mathematics ,Combinatorics ,Frequency partition of a graph ,Partition problem ,Bipartite graph ,Approximation algorithm ,Partition (number theory) ,Inverse ,Disjoint sets ,Graph ,Mathematics - Abstract
In this paper, we continue the investigation proposed in [15] about the approximability of P k partition problems, but focusing here on their complexity. More precisely, we prove that the problem consisting of deciding if a graph of nkvertices has nvertex disjoint simple paths {P 1 , i¾? ,P n } such that each path P i has kvertices is NP -complete, even in bipartite graphs of maximum degree 3. Note that this result also holds when each path P i is chordless in G[V(P i )]. Then, we prove that the optimization version of these problems, denoted by Max P 3 Packing and MaxInduced P 3 Packing , are not in PTAS in bipartite graphs of maximum degree 3. Finally, we propose a 3/2-approximation for Min 3 -PathPartition in general graphs within O(nm+ n2logn) time and a 1/3 (resp., 1/2)-approximation for MaxW P 3 Packing in general (resp., bipartite) graphs of maximum degree 3 within O(i¾?(n,3n/2)n) (resp., O(n2logn)) time, where i¾?is the inverse Ackerman's function and n= |V|, m= |E|. more...
- Published
- 2007
- Full Text
- View/download PDF
25. Finding the (n, k, 0)-Extendability in Bipartite Graphs and Its Application
- Author
-
Yueping Li and Dingjun Lou
- Subjects
Combinatorics ,Discrete mathematics ,Factor-critical graph ,Matching (graph theory) ,Bipartite graph ,Graph ,Blossom algorithm ,Mathematics ,Vertex (geometry) - Abstract
We study the problem of finding the (n,k,0)-extendability in bipartite graphs. Let G be a graph with vertex set V(G). Let n,k,d be non-negative integers such that n + 2k + d ≤ |V(G)| ? 2 and |V(G)| ? n ? d is even. A matching which saturates exactly |V(G)| ? d vertices of G is called a defect-d matching of G. If when deleting any n vertices in V(G) the remaining subgraph contains a matching of k edges and every k-matching can be extended to a defect-d matching, then G is said to be (n,k,d)-extendable. We present an algorithm to find the (n,k,0)-extendability for bipartite graphs. This problem finds application in the circuit design of allocating jobs to processors while some jobs require specified machines to process and some machines are not available. In addition, the connectivity of (n,k,0)-extendable graphs is also discussed. more...
- Published
- 2007
- Full Text
- View/download PDF
26. Mixing 3-Colourings in Bipartite Graphs
- Author
-
Matthew Johnson, Jan van den Heuvel, Luis Cereceda, Brandstädt, Andreas, Kratsch, Dieter, and Müller, Haiko
- Subjects
Combinatorics ,Vertex (graph theory) ,Social connectedness ,Bipartite graph ,Time complexity ,Graph ,Mathematics - Abstract
For a 3-colourable graph G, the 3-colour graph of G, denoted C3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question : given G, how easily can we decide whether or not C3(G) is connected? We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which C3(G) is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time. more...
- Published
- 2007
- Full Text
- View/download PDF
27. Finding Maximum Edge Bicliques in Convex Bipartite Graphs
- Author
-
Jörg-Rüdiger Sack, Hamid Zarrabi-Zadeh, Takeaki Uno, Shuye Pu, and Doron Nussbaum
- Subjects
Combinatorics ,Factor-critical graph ,Discrete mathematics ,Mathematics::Combinatorics ,Edge-transitive graph ,Computer Science::Discrete Mathematics ,Graph power ,Bipartite graph ,Neighbourhood (graph theory) ,Bound graph ,Complete bipartite graph ,Pancyclic graph ,Mathematics - Abstract
A bipartite graph G = (A,B,E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v ∈ A, vertices adjacent to v are consecutive in B. A complete bipartite subgraph of a graph G is called a biclique of G. In this paper, we study the problem of finding the maximum edge-cardinality biclique in convex bipartite graphs. Given a bipartite graph G = (A,B,E) which is convex on B, we present a new algorithm that computes the maximum edge-cardinality biclique of G in O(n log3 n log log n) time and O(n) space, where n = |A|. This improves the current O(n2) time bound available for the problem. more...
- Published
- 2010
- Full Text
- View/download PDF
28. A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small
- Author
-
Raghav Kulkarni
- Subjects
Combinatorics ,Discrete mathematics ,Indifference graph ,Matching (graph theory) ,Chordal graph ,Bipartite graph ,Strong perfect graph theorem ,Maximal independent set ,Cograph ,Algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Hopcroft–Karp algorithm ,Mathematics - Abstract
The perfect matching problem for general graphs reduces to the same for regular graphs. Even finding an NC algorithm for the perfect matching problem in cubic (3-regular) or 4-regular graphs will suffice to solve the general problem (see [DK 92]). For regular bipartite graphs an NC algorithm is already known [LPV 81], while [SW 96] give an NC algorithm for cubic-bipartite graphs. We present a new and conceptually simple parallel algorithm for finding a perfect matching in d-regular bipartite graphs. When d is small (polylogarithmic) our algorithm in fact runs in NC. In particular for cubic-bipartite graphs, our algorithm as well as its analysis become much simpler than the previously known algorithms for the same. Our techniques are completely different from theirs. Interestingly, our algorithm is based on a method used by [MV 00] for finding a perfect matching in planar-bipartite graphs. So, it is remarkable that, circumventing the planarity, we could still make the same approach work for a non-planar subclass of biparitite graphs. more...
- Published
- 2006
- Full Text
- View/download PDF
29. Fuzzy Approach for Image Near-Duplicate Detection Using Gray Level Vertex Matching in Attribute Relational Bipartite Graphs
- Author
-
Bushan L. Raina and Goutam Datta
- Subjects
Vertex (graph theory) ,business.industry ,Computer science ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Pattern recognition ,Fuzzy logic ,Duplicate detection ,Gray level ,Computer Science::Computer Vision and Pattern Recognition ,Bipartite graph ,Source image ,Artificial intelligence ,Vertex detector ,business - Abstract
Shape of different regions of an image depends on the detection of the corners. .However vague information such as blurring, noise etc in an image is normally due to missing curvatures in the regions of image and therefore for the reliable decision for the detection of images in the corresponding domains based on corners in gray level images of source image and its duplicate and for their equivalence we give an algorithm linking it to the set theoretic fuzzy technique. We propose Attribute Relational Bipartite Graph (ARBG) for image near-duplicate (IND) as an important model. The application of the proposed algorithm works well as vertex detectors in their respective two domains. The performance is tested on a number of test images to show the efficiency of the fuzzy based algorithm. more...
- Published
- 2013
- Full Text
- View/download PDF
30. On Non 3-Choosable Bipartite Graphs
- Author
-
Narong Punnim, Wongsakorn Charoenpanitseri, and Chariya Uiyyasathian
- Subjects
Discrete mathematics ,Combinatorics ,Edge coloring ,Matching (graph theory) ,Edge-transitive graph ,Independent set ,Bipartite graph ,Complete coloring ,Complete bipartite graph ,List coloring ,Mathematics - Abstract
In 2003, Fitzpatrick and MacGillivray proved that every complete bipartite graph with fourteen vertices except K 7,7 is 3-choosable and there is the unique 3-list assignment L up to renaming the colors such that K 7,7 is not L-colorable. We present our strategies which can be applied to obtain another proof of their result. These strategies are invented to claim a stronger result that every complete bipartite graph with fifteen vertices except K 7,8 is 3-choosable. We also show all 3-list assignments L such that K 7,8 is not L-colorable. more...
- Published
- 2013
- Full Text
- View/download PDF
31. Completely Independent Spanning Trees on Complete Graphs, Complete Bipartite Graphs and Complete Tripartite Graphs
- Author
-
Shyue-Ming Tang, Jou-Ming Chang, Jinn-Shyong Yang, and Kung-Jui Pai
- Subjects
Discrete mathematics ,Combinatorics ,Pseudoforest ,Trémaux tree ,Triangle-free graph ,Bipartite graph ,Robertson–Seymour theorem ,1-planar graph ,Pancyclic graph ,Mathematics ,Minimum degree spanning tree - Abstract
Let T 1, T 2,…, T k be spanning trees in a graph G. If for any two vertices x, y of G, the paths from x to y in T 1, T 2,…, T k are vertex-disjoint except end vertices x and y, then T 1, T 2,…, T k are called completely independent spanning trees in G. In 2001, Hasunuma gave a conjecture that there are k completely independent spanning trees in any 2k-connected graph. Peterfalvi disproved the conjecture in 2012. In this paper, we shall prove that there are \(\lfloor\frac{n}{2}\rfloor\) completely independent spanning trees in a complete graph with \(n ( \geqslant 4)\) vertices. Then, we prove that there are \(\lfloor\frac{n}{2}\rfloor\) completely independent spanning trees in a complete bipartite graph K m,n where \(m\geqslant n\geqslant 4\). Next, we also prove that there are \(\lfloor\frac{n_1+n_2}{2}\rfloor\) completely independent spanning trees in a complete tripartite graph \(K_{n_3,n_2,n_1}\) where \(n_3\geqslant n_2\geqslant n_1\) and \(n_1+n_2\geqslant 4\). As a result, the Hasunuma’s conjecture holds for complete graphs and complete m-partite graphs where m ∈ {2,3}. more...
- Published
- 2013
- Full Text
- View/download PDF
32. Disjoint Small Cycles in Graphs and Bipartite Graphs
- Author
-
Yunshu Gao and Ding Ma
- Subjects
Physics ,Combinatorics ,Bipartite graph ,Odd graph ,Cograph ,Disjoint sets ,1-planar graph ,Complete bipartite graph ,Pancyclic graph ,Hopcroft–Karp algorithm - Abstract
Let k be a positive integer and let G be a graph of order n ≥ 3k + 1, X be a set of any k distinct vertices of G. It is proved that if \( d\left( x \right) + d\left( y \right) \ge n + 2k - 2\) for any pair of nonadjacent vertices \(x,y \in V\left( G \right)\), then G contains k disjoint cycles T 1, ⋯ ,T k such that each cycle contains exactly one vertex in X, and \(\left| {{T_i}} \right| = 3\) for each 1 ≤ i ≤ k or \(\left| {{T_k}} \right| = 4\) and the rest are all triangles. We also obtained two results about disjoint 6-cycles in a bipartite graph. more...
- Published
- 2013
- Full Text
- View/download PDF
33. Sphere Anchored Map: A Visualization Technique for Bipartite Graphs in 3D
- Author
-
Takao Ito, Jiro Tanaka, and Kazuo Misue
- Subjects
Condensed Matter::Soft Condensed Matter ,Combinatorics ,Set (abstract data type) ,Computer science ,Bipartite graph ,Circumference ,Graph ,Visualization - Abstract
Circular anchored maps have been proposed as a drawing technique to acquire knowledge from bipartite graphs, where nodes in one set are arranged on a circumference. However, the readability decreases when large-scale graphs are drawn. To maintain the readability in drawing large-scale graphs, we developed "sphere anchored maps," in which nodes in one set are arranged on a sphere. We describe the layout method for sphere anchored maps and the results of our user study. The results of our study revealed that more clusters of free nodes can be found using sphere anchored maps than using circular anchored maps. Thus, our maps have high readability, particularly around anchors. more...
- Published
- 2009
- Full Text
- View/download PDF
34. Bipartite Graphs of Large Clique-Width
- Author
-
Nicholas Korpelainen and Vadim V. Lozin
- Subjects
Discrete mathematics ,Computer science ,Biregular graph ,Strong perfect graph theorem ,Clique (graph theory) ,Tree-depth ,Complete bipartite graph ,Combinatorics ,Treewidth ,Computer Science::Discrete Mathematics ,Chordal graph ,Clique-width ,3-dimensional matching ,Triangle-free graph ,Bipartite graph ,Cograph ,Blossom algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Recently, several constructions of bipartite graphs of large clique-width have been discovered in the literature. In the present paper, we propose a general framework for developing such constructions and use it to obtain new results on this topic. more...
- Published
- 2009
- Full Text
- View/download PDF
35. Towards Optimal Degree-Distributions for Left-Perfect Matchings in Random Bipartite Graphs
- Author
-
Martin Dietzfelbinger and Michael Rink
- Subjects
Combinatorics ,Physics ,Distribution (mathematics) ,Degree (graph theory) ,Integer ,Multigraph ,Bipartite graph ,Interval (mathematics) ,Complete bipartite graph ,Bar (unit) - Abstract
Consider a random bipartite multigraph G with n left nodes and m ≥ n ≥ 2 right nodes. Each left node x has d x ≥ 1 random right neighbors. The average left degree \(\bar{{\mathrm{\scriptstyle\Delta}}}\) is fixed, \(\bar{{\mathrm{\scriptstyle\Delta}}}\geq2\). We ask whether for the probability that G has a left-perfect matching it is advantageous not to fix d x for each left node x but rather choose it at random according to some (cleverly chosen) distribution. We show the following, provided that the degrees of the left nodes are independent: If \(\bar{{\mathrm{\scriptstyle\Delta}}}\) is an integer then it is optimal to use a fixed degree of \(\bar{{\mathrm{\scriptstyle\Delta}}}\) for all left nodes. If \(\bar{{\mathrm{\scriptstyle\Delta}}}\) is non-integral then an optimal degree-distribution has the property that each left node x has two possible degrees, \(\ensuremath{\lfloor \bar{{\mathrm{\scriptstyle\Delta}}}\rfloor}\) and \(\ensuremath{\lceil \bar{{\mathrm{\scriptstyle\Delta}}}\rceil}\), with probability p x and 1 − p x , respectively, where p x is from the closed interval [0,1] and the average over all p x equals \(\ensuremath{\lceil \bar{{\mathrm{\scriptstyle\Delta}}}\rceil}-\bar{{\mathrm{\scriptstyle\Delta}}}\). Furthermore, if n = c·m and \(\bar{{\mathrm{\scriptstyle\Delta}}}>2\) is constant, then each distribution of the left degrees that meets the conditions above determines the same threshold \(c^*({\bar{{\mathrm{\scriptstyle\Delta}}}})\) that has the following property as n goes to infinity: If \(c c^*({\bar{{\mathrm{\scriptstyle\Delta}}}})\) then there exists no left-perfect matching with high probability. The threshold \(c^*({\bar{{\mathrm{\scriptstyle\Delta}}}})\) is the same as the known threshold for offline k-ary cuckoo hashing for integral or non-integral \(k=\bar{{\mathrm{\scriptstyle\Delta}}}\). more...
- Published
- 2012
- Full Text
- View/download PDF
36. Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
- Author
-
Ching-Chen Kuo and Hsueh-I Lu
- Subjects
Combinatorics ,Discrete mathematics ,Common neighbor ,Bounded function ,Bipartite graph ,Constant (mathematics) ,Glauber ,Graph ,Mixing (physics) ,Mathematics - Abstract
Let G be an n-node graph with maximum degree Δ. The Glauber dynamics for G, defined by Jerrum, is a Markov chain over the k-colorings of G. Many classes of G on which the Glauber dynamics mixes rapidly have been identified. Recent research efforts focus on the important case that Δ ≥ dlog2 n holds for some sufficiently large constant d. We add the following new results along this direction, where e can be any constant with 0 < e < 1. Let α ≈ 1.645 be the root of (1 − e − 1/x )2 + 2x e − 1/x = 2. If G is regular and bipartite and k ≥ (α + e)Δ, then the mixing time of the Glauber dynamics for G is O(nlogn). Let β ≈ 1.763 be the root of x = e 1/x . If the number of common neighbors for any two adjacent nodes of G is at most \(\frac{\epsilon^{1.5}\Delta}{360e}\) and k ≥ (1 + e)βΔ, then the mixing time of the Glauber dynamics is O(nlogn). more...
- Published
- 2012
- Full Text
- View/download PDF
37. Online Coloring of Bipartite Graphs with and without Advice
- Author
-
Hans-Joachim Böckenhauer, Maria Paola Bianchi, Juraj Hromkovič, and Lucia Keller
- Subjects
Combinatorics ,Greedy coloring ,Computer science ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Bipartite graph ,Graph coloring ,Complete coloring ,Online algorithm ,Advice (complexity) ,Upper and lower bounds ,MathematicsofComputing_DISCRETEMATHEMATICS ,List coloring - Abstract
In the online version of the well-known graph coloring problem, the vertices appear one after the other together with the edges to the already known vertices and have to be irrevocably colored immediately after their appearance. We consider this problem on bipartite, i.e., two-colorable graphs. We prove that 1.13747·log2 n colors are necessary for any deterministic online algorithm to color any bipartite graph on n vertices, thus improving on the previously known lower bound of log2 n + 1 for sufficiently large n. more...
- Published
- 2012
- Full Text
- View/download PDF
38. Optimizing a Radial Layout of Bipartite Graphs for a Tool Visualizing Security Alerts
- Author
-
Jean-Marc Robert, Marie-Claire Willig, Maxime Dumas, and Michael J. McGuffin
- Subjects
Quantities of information ,Theoretical computer science ,Graph drawing ,Computer science ,Bipartite graph ,Clutter ,Enhanced Data Rates for GSM Evolution ,Minification ,MathematicsofComputing_DISCRETEMATHEMATICS ,Visualization - Abstract
Effective tools are crucial for visualizing large quantities of information. While developing these tools, numerous graph drawing problems emerge. We present solutions for reducing clutter in a radial visualization of a bipartite graph representing the alerts generated by an IDS protecting a computer network. Our solutions rely essentially on (i) unambiguous edge bundling to reduce the number of edges to display and (ii) the minimization of the total sum of the edge lengths. more...
- Published
- 2012
- Full Text
- View/download PDF
39. An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs
- Author
-
Xiao-Shuang Xu, Jianer Chen, and Jianxin Wang
- Subjects
Combinatorics ,Vertex (graph theory) ,Polynomial time approximation algorithm ,Discrete mathematics ,Vertex cover ,Bipartite graph ,Approximation algorithm ,Feedback vertex set ,Complete bipartite graph ,Edge cover ,Mathematics - Abstract
The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant Ɛ > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (ku, kl), our algorithm constructs a vertex cover of size (ku*, kl* ), satisfying max{ku*/ku, kl* /kl} ≤ 1 + Ɛ. more...
- Published
- 2008
- Full Text
- View/download PDF
40. Image Tagging Using PageRank over Bipartite Graphs
- Author
-
Christian Bauckhage
- Subjects
Color image ,business.industry ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Markov process ,Pattern recognition ,Object (computer science) ,Ranking (information retrieval) ,law.invention ,symbols.namesake ,PageRank ,law ,Histogram ,Pattern recognition (psychology) ,Bipartite graph ,symbols ,Artificial intelligence ,business ,Mathematics - Abstract
We consider the problem of automatic image tagging for online services and explore a prototype-based approach that applies ideas from manifold ranking. Since algorithms for ranking on graphs or manifolds often lack a way of dealing with out of sample data, they are of limited use for pattern recognition. In this paper, we therefore propose to consider diffusion processes over bipartite graphs which allow for a dual treatment of objects and features. As with Google's PageRank, this leads to Markov processes over the prototypes. In contrast to related methods, our model provides a Bayesian interpretation of the transition matrix and enables the ranking and consequently the classification of unknown entities. By design, the method is tailored to histogram features and we apply it to histogram-based color image analysis. Experiments with images downloaded from flickr.com illustrate object localization in realistic scenes. more...
- Published
- 2008
- Full Text
- View/download PDF
41. Study on the Some Labelings of Complete Bipartite Graphs
- Author
-
QianTai Yan, GuangHai Li, and WuZhuang Li
- Subjects
Combinatorics ,Discrete mathematics ,Vertex (graph theory) ,Graceful labeling ,Edge-graceful labeling ,Bipartite graph ,Empty set ,Complete bipartite graph ,Mathematics - Abstract
If the vertex set V of G = can be divided into two un empty sets X and Y, X ∪ Y = V,X ∩ Y = ∅, but also two nodes of every edge belong to X and Y separately, the G is called bipartite graph. If ∀ x i ∈ X, y i ∈ Y, (x i , y i ) ∈ E then G is called complete bipartite graph. if ∣ X ∣ = m,∣ Y ∣ = n, the G is marked K m,n . In this paper the graceful labeling, k-graceful labeling, odd graceful labeling and odd strongly harmonious labeling are given. more...
- Published
- 2011
- Full Text
- View/download PDF
42. Anchored Maps: Visualization Techniques for Drawing Bipartite Graphs
- Author
-
Kazuo Misue
- Subjects
Computer science ,Biregular graph ,Voltage graph ,Complete bipartite graph ,Simplex graph ,Quantitative Biology::Cell Behavior ,law.invention ,Quantitative Biology::Subcellular Processes ,Condensed Matter::Soft Condensed Matter ,Combinatorics ,Edge-transitive graph ,Graph drawing ,law ,ComputerApplications_MISCELLANEOUS ,Clique-width ,Line graph ,Bipartite graph ,Force-directed graph drawing ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
A method of drawing anchored maps for bipartite graphs is presented. Suppose that the node set of a bipartite graph is divided into set A and set B. On an anchored map of the bipartite graph, the nodes in A, which are called "anchors," are arranged on the circumference, and the nodes in B, which are called "free nodes," are arranged at suitable positions in relation to the adjacent anchors. This article describes aesthetic criteria that are employed according to the purpose of drawing anchored maps and indices which are used to arrange the anchors so that they satisfy the criteria. It also shows an example of taking overviews of networks by using the developed technique. more...
- Published
- 2007
- Full Text
- View/download PDF
43. On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
- Author
-
Yi-Chuan Yang and Sheng-Lung Peng
- Subjects
Discrete mathematics ,Mathematics::Combinatorics ,Computer Science::Computational Complexity ,Tree-depth ,1-planar graph ,Complete bipartite graph ,Treewidth ,Combinatorics ,Pathwidth ,Computer Science::Discrete Mathematics ,Partial k-tree ,Clique-width ,Bipartite graph ,Computer Science::Data Structures and Algorithms ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
In this paper we explore the biclique structure of a biconvex bipartite graph G. We define two concatenation operators on bicliques of G. According to these operations, we show that G can be decomposed into two chain graphs GL and GR, and a bipartite permutation graph GP. Using this representation, we propose linear-time algorithms for the treewidth and pathwidth problems on biconvex bipartite graphs. more...
- Published
- 2007
- Full Text
- View/download PDF
44. Tree Spanners for Bipartite Graphs and Probe Interval Graphs
- Author
-
Van Bang Le, Hoang-Oanh Le, Feodor F. Dragan, Andreas Brandstädt, and Ryuhei Uehara
- Subjects
Block graph ,Combinatorics ,Discrete mathematics ,Pathwidth ,K-ary tree ,Trémaux tree ,Chordal graph ,Gomory–Hu tree ,Computer Science::Computational Geometry ,Computer Science::Data Structures and Algorithms ,Tree-depth ,Complete bipartite graph ,Mathematics - Abstract
A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE–free graph has a tree 3-spanner, which can be found in linear time. The best known before results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in O(m log n) time. more...
- Published
- 2003
- Full Text
- View/download PDF
45. Bipartite Graphs for Monitoring Clusters Transitions
- Author
-
João Gama and Márcia Oliveira
- Subjects
Important research ,Computer science ,business.industry ,Bipartite graph ,Graph theory ,Data mining ,Artificial intelligence ,Change mining ,Machine learning ,computer.software_genre ,Cluster analysis ,business ,computer - Abstract
The study of evolution has become an important research issue, especially in the last decade, due to a greater awareness of our world’s volatility. As a consequence, a new paradigm has emerged to respond more effectively to a class of new problems in Data Mining. In this paper we address the problem of monitoring the evolution of clusters and propose the MClusT framework, which was developed along the lines of this new Change Mining paradigm. MClusT includes a taxonomy of transitions, a tracking method based in Graph Theory, and a transition detection algorithm. To demonstrate its feasibility and applicability we present real world case studies, using datasets extracted from Banco de Portugal and the Portuguese Institute of Statistics. We also test our approach in a benchmark dataset from TSDL. The results are encouraging and demonstrate the ability of MClusT framework to provide an efficient diagnosis of clusters transitions. more...
- Published
- 2010
- Full Text
- View/download PDF
46. A 27/26-Approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs
- Author
-
Marek Kubale, Robert Janczewski, Michał Małafiejski, and Krzysztof Giaro
- Subjects
Combinatorics ,Discrete mathematics ,Mathematics::Combinatorics ,Matching (graph theory) ,Degree (graph theory) ,Computer Science::Discrete Mathematics ,Chordal graph ,Bipartite graph ,Approximation algorithm ,Chromatic scale ,Complete bipartite graph ,Hopcroft–Karp algorithm ,Mathematics - Abstract
We consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with ? ? 5, but polynomial on bipartite graphs with ? ? 3, for which we construct an O(n2)-time algorithm. Hence, we tighten the borderline of intractability for this problem on bipartite graphs with bounded degree, namely: the case ? = 3 is easy, ? = 5 is hard. Moreover, we construct a 27/26-approximation algorithm for this problem thus improving the best known approximation ratio of 10/9. more...
- Published
- 2002
- Full Text
- View/download PDF
47. A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs
- Author
-
Kenjiro Takazawa
- Subjects
Discrete mathematics ,Factor-critical graph ,Matching (graph theory) ,Complete bipartite graph ,Combinatorics ,Edge-transitive graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Perfect graph ,Bipartite graph ,Algorithm ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics ,Forbidden graph characterization ,Distance-hereditary graph - Abstract
For a simple bipartite graph and an integer t ≥ 2, we consider the problem of finding a minimum-weight t-factor under the restriction that it contains no complete bipartite graph Kt, t as a subgraph. When t = 2, this problem amounts to the minimum-weight square-free 2-factor problem in a bipartite graph, which is NP-hard. We propose, however, a strongly polynomial algorithm for a certain case where the weight vector is vertex-induced on any subgraph isomorphic to Kt, t. The algorithm adapts the unweighted algorithms of Hartvigsen and Pap, and a primal-dual approach to the minimum-cost flow problem. The algorithm is fully combinatorial, and thus provides a dual integrality theorem, which is tantamount to Makai's theorem dealing with maximum-weight Kt, t-free t-matchings. more...
- Published
- 2008
- Full Text
- View/download PDF
48. Covering the Edges of Bipartite Graphs Using K 2,2 Graphs
- Author
-
Dorit S. Hochbaum and Asaf Levin
- Subjects
Discrete mathematics ,Matching (graph theory) ,Vertex cover ,0102 computer and information sciences ,01 natural sciences ,Feedback arc set ,Complete bipartite graph ,Edge cover ,Combinatorics ,010104 statistics & probability ,010201 computation theory & mathematics ,Covering graph ,Independent set ,Bipartite graph ,0101 mathematics ,Mathematics - Abstract
We consider an optimization problem arising in the design of optical networks. We are given a bipartite graph G = (L,R,E) over the node set L ∪ R where the edge set is E ⊆ {[u, v] : u ∈ L, v ∈ R}, and implicitly a collection of all four-nodes cycles in the complete graph over V. The goal is to find a minimum size sub-collection of graphs G1,G2, . . . , Gp where for each i Gi is isomorphic to a cycle over four nodes, and such that the edge set E is contained in the union (over all i) of the edge sets of Gi. Noting that every four edge cycle can be a part of the solution, this covering problem is a special case of the unweighted 4-set cover problem. This specialization allows us to obtain an improved approximation guarantee. Whereas the currently best known approximation algorithm for the general unweighted 4-set cover problem has an approximation ratio of H4 - 196/390 ≅ 1.58077 (where Hp denotes the p-th harmonic number), we show that for every Ɛ > 0 there is a polynomial time (13/10 + Ɛ)-approximation algorithm for our problem. Our analysis of the greedy algorithm shows that when applied to covering a bipartite graph using copies of Kq,q bicliques, it returns a feasible solution whose cost is at most (Hq2 -Hq +1)OPT +1 where OPT denotes the optimal cost, thus improving the approximation bound by a factor of almost 2. more...
- Published
- 2008
- Full Text
- View/download PDF
49. Automatic Summarization of Rushes Video Using Bipartite Graphs
- Author
-
Noel E. O'Connor, Liang Bai, Songyang Lao, and Alan F. Smeaton
- Subjects
Ground truth ,Information retrieval ,business.industry ,Computer science ,Digital video ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Context (language use) ,Pattern recognition ,Information technology ,02 engineering and technology ,TRECVID ,Automatic summarization ,Image processing ,Filter (video) ,0202 electrical engineering, electronic engineering, information engineering ,Bipartite graph ,Redundancy (engineering) ,020201 artificial intelligence & image processing ,Segmentation ,Computer software ,Artificial intelligence ,business - Abstract
In this paper we present a new approach for automatic summarization of rushes video. Our approach is composed of three main steps. First, based on a temporal segmentation, we filter sub-shots with low information content not likely to be useful in a summary. Second, a method using maximal matching in a bipartite graph is adapted to measure similarity between the remaining shots and to minimize inter-shot redundancy by removing repetitive retake shots common in rushes content. Finally, the presence of faces and the motion in-tensity are characterised in each sub-shot. A measure of how representative the sub-shot is in the context of the overall video is then proposed. Video summaries composed of keyframe slideshows are then generated. In order to evaluate the effectiveness of this approach we re-run the evaluation carried out by the TREC, using the same dataset and evaluation metrics used in the TRECVID video summarization task in 2007 but with our own assessors. Results show that our approach leads to a significant improvement in terms of the fraction of the TRECVID summary ground truth included and is competitive with other approaches in TRECVID 2007. more...
- Published
- 2008
- Full Text
- View/download PDF
50. Directed Variants of Forests and Bipartite Graphs
- Author
-
Jakob Jonsson
- Subjects
Combinatorics ,Bipartite graph - Published
- 2008
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.