Generalized median graphs and applications

Lopamudra Mukherjee (), Vikas Singh (), Jiming Peng (), Jinhui Xu (), Michael J. Zeitz () and Ronald Berezney ()
Additional contact information
Lopamudra Mukherjee: University of Wisconsin–Whitewater
Vikas Singh: University of Wisconsin–Madison
Jiming Peng: University of Illinois at Urbana-Champaign
Jinhui Xu: The State University of New York at Buffalo
Michael J. Zeitz: The State University of New York at Buffalo
Ronald Berezney: The State University of New York at Buffalo

Journal of Combinatorial Optimization, 2009, vol. 17, issue 1, No 3, 44 pages

Abstract: Abstract We study the so-called Generalized Median graph problem where the task is to construct a prototype (i.e., a ‘model’) from an input set of graphs. While our primary motivation comes from an important biological imaging application, the problem effectively captures many vision (e.g., object recognition) and learning problems, where graphs are increasingly being adopted as a powerful representation tool. Existing techniques for his problem are evolutionary search based; in this paper, we propose a polynomial time algorithm based on a linear programming formulation. We propose an additional algorithm based on a bi-level method to obtain solutions arbitrarily close to the optimal in (worst case) non-polynomial time. Within this new framework, one can optimize edit distance functions that capture similarity by considering vertex labels as well as he graph structure simultaneously. We first discuss experimental evaluations in context of molecular image analysis problems—he methods will provide the basis for building a topological map of all 23 pairs of the human chromosome. Later, we include (a) applications to other biomedical problems and (b) evaluations on a public pattern recognition graph database.

Keywords: Median graph; Graph edit distance; Graph matching; Prototype building; Chromosome organization; Cell-nucleus imaging (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9184-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:17:y:2009:i:1:d:10.1007_s10878-008-9184-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9184-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().