Search

Your search keyword '"Bipartite Match"' showing total 56 results
Start Over Descriptor "Bipartite Match"

Refine your results

more »

more »

56 results on '"Bipartite Match"'

4. Engineering a Bipartite Matching Algorithm in the Semi-Streaming Model

Author

Kliemann, Lasse, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kliemann, Lasse, editor, and Sanders, Peter, editor

Published
2016
Full Text
View/download PDF

5. Maximum Matching in Turnstile Streams

Author

Konrad, Christian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bansal, Nikhil, editor, and Finocchi, Irene, editor

Published
2015
Full Text
View/download PDF

6. Secretary Markets with Local Information

Author

Chen, Ning, Hoefer, Martin, Künnemann, Marvin, Lin, Chengyu, Miao, Peihan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Halldórsson, Magnús M., editor, Iwama, Kazuo, editor, Kobayashi, Naoki, editor, and Speckmann, Bettina, editor

Published
2015
Full Text
View/download PDF

7. The Power of Rejection in Online Bottleneck Matching

Author

Anthony, Barbara M., Chung, Christine, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Zhang, Zhao, editor, Wu, Lidong, editor, Xu, Wen, editor, and Du, Ding-Zhu, editor

Published
2014
Full Text
View/download PDF

11. RNA Tree Comparisons via Unrooted Unordered Alignments

Author

Milo, Nimrod, Zakov, Shay, Katzenelson, Erez, Bachmat, Eitan, Dinitz, Yefim, Ziv-Ukelson, Michal, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Raphael, Ben, editor, and Tang, Jijun, editor

Published
2012
Full Text
View/download PDF

12. Maximum Matching in Semi-streaming with Few Passes

Author

Konrad, Christian, Magniez, Frédéric, Mathieu, Claire, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gupta, Anupam, editor, Jansen, Klaus, editor, Rolim, José, editor, and Servedio, Rocco, editor

Published
2012
Full Text
View/download PDF

13. Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations

Author

Bollig, Beate, Gillé, Marc, Pröger, Tobias, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Agrawal, Manindra, editor, Cooper, S. Barry, editor, and Li, Angsheng, editor

Published
2012
Full Text
View/download PDF

14. Flow-Based Combinatorial Chance Constraints

Author

Cire, Andre A., Coban, Elvin, van Hoeve, Willem-Jan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Beldiceanu, Nicolas, editor, Jussien, Narendra, editor, and Pinson, Éric, editor

Published
2012
Full Text
View/download PDF

15. Space-Efficient Approximation Scheme for Circular Earth Mover Distance

Author

Brody, Joshua, Liang, Hongyu, Sun, Xiaoming, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Fernández-Baca, David, editor

Published
2012
Full Text
View/download PDF

16. On the Integrality Gap of the Subtour LP for the 1,2-TSP

Author

Qian, Jiawei, Schalekamp, Frans, Williamson, David P., van Zuylen, Anke, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Fernández-Baca, David, editor

Published
2012
Full Text
View/download PDF

17. On Tree-Constrained Matchings and Generalizations

Author

Canzar, Stefan, Elbassioni, Khaled, Klau, Gunnar W., Mestre, Julián, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Henzinger, Monika, editor, and Sgall, Jiří, editor

Published
2011
Full Text
View/download PDF

19. Robust Matchings and Matroid Intersections

Author

Fujita, Ryo, Kobayashi, Yusuke, Makino, Kazuhisa, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, de Berg, Mark, editor, and Meyer, Ulrich, editor

Published
2010
Full Text
View/download PDF

20. On Map Labeling with Leaders

Author

Kaufmann, Michael, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Albers, Susanne, editor, Alt, Helmut, editor, and Näher, Stefan, editor

Published
2009
Full Text
View/download PDF

21. Maximum Bipartite Flow in Networks with Adaptive Channel Width

Author

Azar, Yossi, Mądry, Aleksander, Moscibroda, Thomas, Panigrahi, Debmalya, Srinivasan, Aravind, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Albers, Susanne, editor, Marchetti-Spaccamela, Alberto, editor, Matias, Yossi, editor, Nikoletseas, Sotiris, editor, and Thomas, Wolfgang, editor

Published
2009
Full Text
View/download PDF

22. Two-Level Push-Relabel Algorithm for the Maximum Flow Problem

Author

Goldberg, Andrew V., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Goldberg, Andrew V., editor, and Zhou, Yunhong, editor

Published
2009
Full Text
View/download PDF

23. Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines

Author

Plaxton, C. Greg, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Damgård, Ivan, editor, Goldberg, Leslie Ann, editor, Halldórsson, Magnús M., editor, Ingólfsdóttir, Anna, editor, and Walukiewicz, Igor, editor

Published
2008
Full Text
View/download PDF

24. BioDIFF: An Effective Fast Change Detection Algorithm for Biological Annotations

Author

Song, Yang, Bhowmick, Sourav S., Dewey, C. Forbes, Jr., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kotagiri, Ramamohanarao, editor, Krishna, P. Radha, editor, Mohania, Mukesh, editor, and Nantajeewarawat, Ekawit, editor

Published
2007
Full Text
View/download PDF

26. Popular Matchings in the Capacitated House Allocation Problem

Author

Manlove, David F., Sng, Colin T. S., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Azar, Yossi, editor, and Erlebach, Thomas, editor

Published
2006
Full Text
View/download PDF

27. DTD-Diff: A Change Detection Algorithm for DTDs

Author

Leonardi, Erwin, Hoai, Tran T., Bhowmick, Sourav S., Madria, Sanjay, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Li Lee, Mong, editor, Tan, Kian-Lee, editor, and Wuwongse, Vilas, editor

Published
2006
Full Text
View/download PDF

28. Quantum Algorithms for Matching and Network Flows

Author

Ambainis, Andris, Špalek, Robert, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Durand, Bruno, editor, and Thomas, Wolfgang, editor

Published
2006
Full Text
View/download PDF

29. Optimal Hypergraph Tree-Realization

Author

Korach, Ephraim, Razgon, Margarita, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Kratsch, Dieter, editor

Published
2005
Full Text
View/download PDF

40. Auction Based Mechanisms for Dynamic Task Assignments in Expert Crowdsourcing

Author

Boi Faltings and Sujit Gujar

Subjects
Matching (statistics), Competitive analysis, business.industry, Computer science, media_common.quotation_subject, Bipartite match, Payment, Machine learning, computer.software_genre, Crowdsourcing, Data science, Task (project management), If and only if, Artificial intelligence, business, Set (psychology), computer, media_common
Abstract

Crowdsourcing marketplaces link large populations of workers to an even larger number of tasks. Thus, it is necessary to have mechanisms for matching workers with interesting and suitable tasks. Earlier work has addressed the problem of finding optimal workers for a given set of tasks. However, workers also have preferences and will stay with a platform only if it gives them interesting tasks. We therefore analyze several matching mechanisms that take into account workers’ preferences as well. We propose that the workers pay premiums to get preferred matches and auction-based models where preferences are expressed through variations of the payment for a task. We analyze the properties of two matching different mechanisms: Split Dynamic VCG (SDV) and e-Auction. We compare both the mechanisms with Arrival Priority Serial Dictatorship (APSD) empirically for efficiency.

Published
2017
Full Text
View/download PDF

41. Some complexity theoretic aspects of AC rewriting

Author

Verma, Rakesh M., Ramakrishnan, I. V., Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Monien, B., editor, and Cori, R., editor

Published
1989
Full Text
View/download PDF

42. Subtree isomorphism is in random NC

Author

Gibbons, Phillip B., Miller, Gary L., Karp, Richard M., Soroker, Danny, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, and Reif, John H., editor

Published
1988
Full Text
View/download PDF

44. Maximum Matching in Turnstile Streams

Author

Christian Konrad

Subjects
Discrete mathematics, Combinatorics, Turnstile, Logarithm, Bipartite graph, Bipartite match, Streaming algorithm, Graph, Constant error, Mathematics, Randomized algorithm
Abstract

We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass 2-approximation streaming algorithm can be easily obtained with space O(n logn), where n denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space O(n3/2 − δ) is granted, for every δ > 0. Specifically, for every 0 ≤ e ≤ 1, we show that in the one-pass turnstile streaming model, in order to compute a O(n e )-approximation, space Ω(n3/2 − 4e) is required for constant error randomized algorithms, and, up to logarithmic factors, space \(\tilde{\mathrm{O}}( n^{2-2\epsilon} )\) is sufficient.

Published
2015
Full Text
View/download PDF

45. List of Problems and Algorithms

Author

Magnus Lie Hetland

Subjects
List update problem, Theoretical computer science, Knapsack problem, Computer science, Bipartite match, Self-organizing list
Published
2014
Full Text
View/download PDF

46. Iterative Compression, and Measure and Conquer, for Minimization Problems

Author

Rodney G. Downey and Michael R. Fellows

Subjects
Gray code, Computer science, Vertex cover, Measure and conquer, Iterative compression, ComputerApplications_COMPUTERSINOTHERSYSTEMS, Data_CODINGANDINFORMATIONTHEORY, Minification, Bipartite match, Algorithm, Computer Science::Databases
Abstract

We introduce the technique of iterative compression. We illustrate how this can be combined with analytical techniques such as measure and conquer.

Published
2013
Full Text
View/download PDF

47. RNA Tree Comparisons via Unrooted Unordered Alignments

Author

Eitan Bachmat, Nimrod Milo, Michal Ziv-Ukelson, Shay Zakov, Erez Katzenelson, and Yefim Dinitz

Subjects
Combinatorics, Discrete mathematics, Tree (data structure), Current (mathematics), Tree edit distance, Source code, media_common.quotation_subject, Node (circuits), Bipartite match, Time complexity, Tree alignment, Mathematics, media_common
Abstract

We generalize some current approaches for RNA tree alignment, which are traditionally confined to ordered rooted mappings, to also consider unordered unrooted mappings. We define the Homeomorphic Subtree Alignment problem, and present a new algorithm which applies to several modes, including global or local, ordered or unordered, and rooted or unrooted tree alignments. Our algorithm generalizes previous algorithms that either solved the problem in an asymmetric manner, or were restricted to the rooted and/or ordered cases. Focusing here on the most general unrooted unordered case, we show that our algorithm has an O(nTnS min (dT, dS)) time complexity, where nT and nS are the number of nodes and dT and dS are the maximum node degrees in the input trees T and S, respectively. This maintains (and slightly improves) the time complexity of previous, less general algorithms for the problem. Supplemental materials, source code, and web-interface for our tool are found in http://www.cs.bgu.ac.il/~negevcb/FRUUT.

Published
2012
Full Text
View/download PDF

48. On the Integrality Gap of the Subtour LP for the 1,2-TSP

Author

Frans Schalekamp, David P. Williamson, Anke van Zuylen, and Jiawei Qian

Subjects
Discrete mathematics, FOS: Computer and information sciences, 021103 operations research, Conjecture, Linear programming, Triangle inequality, General Mathematics, 0211 other engineering and technologies, Structure (category theory), 0102 computer and information sciences, 02 engineering and technology, Bipartite match, 01 natural sciences, Travelling salesman problem, Combinatorics, Linear programming relaxation, 010201 computation theory & mathematics, 90C27, 90C59, 90C05, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Special case, F.2.0, Software, Mathematics
Abstract

In this paper, we study the integrality gap of the subtour LP relaxation for the traveling salesman problem in the special case when all edge costs are either 1 or 2. For the general case of symmetric costs that obey triangle inequality, a famous conjecture is that the integrality gap is 4/3. Little progress towards resolving this conjecture has been made in thirty years. We conjecture that when all edge costs $c_{ij}\in \{1,2\}$, the integrality gap is $10/9$. We show that this conjecture is true when the optimal subtour LP solution has a certain structure. Under a weaker assumption, which is an analog of a recent conjecture by Schalekamp, Williamson and van Zuylen, we show that the integrality gap is at most $7/6$. When we do not make any assumptions on the structure of the optimal subtour LP solution, we can show that integrality gap is at most $5/4$; this is the first bound on the integrality gap of the subtour LP strictly less than $4/3$ known for an interesting special case of the TSP. We show computationally that the integrality gap is at most $10/9$ for all instances with at most 12 cities., Changes wrt previous version: upper bound on integrality gap improved to 5/4 (using the same techniques as in the previous version)

Published
2011

49. Matchings, Cuts, and Flows

Author

Magnus Lie Hetland

Subjects
Disjoint path, Core (game theory), Mathematical optimization, Computer science, Path (graph theory), Maximum flow problem, Bipartite graph, Disjoint sets, Bipartite match, Dual (category theory)
Abstract

While the previous chapter gave you several algorithms for a single problem, this chapter describes a single algorithm with many variations and applications. The core problem is that of finding maximum flow in a network, and the main solution strategy I’ll be using is the augmenting path method of Ford and Fulkerson. Before tackling the full problem, I’ll guide you through two simpler problems, which are basically special cases (they’re easily reduced to maximum flow). These problems, bipartite matching and disjoint paths, have many applications themselves and can be solved by more specialized algorithms. You’ll also see that the max-flow problem has a dual, the min-cut problem, which means that you’ll automatically solve both problems at the same time. The min-cut problem has several interesting applications that seem very different from those of max-flow, even if they are really closely related. Finally, I’ll give you some pointers on one way of extending the max-flow problem, by adding costs, and looking for the cheapest of the maximum flows, paving the way for applications such as mincost bipartite matching.

Published
2010
Full Text
View/download PDF

50. Selected Applications of Graph-Based Tracking Methods for Cancer Research

Author

Lilian Soon and Pascal Vallotton

Subjects
business.industry, Computer science, Graph based, Bipartite match, Machine learning, computer.software_genre, Automation, Software, Video tracking, Graph (abstract data type), Artificial intelligence, Cell tracking, business, computer
Abstract

Cell appearance is highly variable, particularly for cancer cells. Consequently, massive amounts of image data need to be screened rapidly and reproducibly to ascertain phenotypic information of interest. This demands a high level of automation and chosen image analysis techniques.A very relevant phenotype for cancer is motile behaviour as it is a fundamental ingredient of its development. We aim to measure normal and abnormal motile processes, identify small molecules and genotypes that modulate these processes, and develop mathematical models of the disease towards identifying specific targets or target sets. Here, we describe the use and principles underlying representative software tools to read motile phenotypes from time-lapse data, with emphasis on improved graph-based tracking methods.

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results