Optimizing Computation of Minimum Cut in Graphs with Grid Topology
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F13%3A00192353" target="_blank" >RIV/68407700:21230/13:00192353 - isvavai.cz</a>
Result on the web
<a href="http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8,533,139.PN.&OS=PN/8,533,139&RS=PN/8,533,139" target="_blank" >http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8,533,139.PN.&OS=PN/8,533,139&RS=PN/8,533,139</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Optimizing Computation of Minimum Cut in Graphs with Grid Topology
Original language description
Approaches for optimizing computation of minimum cut or maximum flow on graphs comprising a plurality of nodes and edges with grid-like topologies are disclosed. Embodiments exploit the regular structure of input graphs to reduce the memory bandwidth - amain bottleneck of popular max-flow/min-cut algorithms based on finding augmenting paths on a residual graph (such as Ford-Fulkerson [1956] or Boykov-Kolmogorov [2004]). Disclosed embodiments allow more than 200% speed-up without sacrificing optimalityof the final solution, which is crucial for many computer vision and graphics applications. Method and system embodiments replace standard linked list representation of general graphs with a set of compact data structures with blocked memory layout thatenables fixed ordering of edges and implicit branchless addressing of nodes. The embodiments are orthogonal to other optimizations such as parallel processing or hierarchical methods and can be readily plugged into existing min-cut/max-fl
Czech name
—
Czech description
—
Classification
Type
P - Patent
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/TE01020415" target="_blank" >TE01020415: V3C - Visual Computing Competence Center</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Patent/design ID
US8,533,139
Publisher
US001 -
Publisher name
United States Patent and Trademark Office (USPTO)
Place of publication
Alexandria
Publication country
US - UNITED STATES
Date of acceptance
Sep 10, 2013
Owner name
ČVUT FEL (DCGI)
Method of use
B - Výsledek je využíván orgány státní nebo veřejné správy
Usage type
A - K využití výsledku jiným subjektem je vždy nutné nabytí licence