Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Full text

Pdf (811 KB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 2 (April 1972) table of contents

Pages: 248 - 264

Year of Publication: 1972

ISSN:0004-5411

Authors

Jack Edmonds	Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada
Richard M. Karp	College of Engineering, Operations Research Center, University of California, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 49, Downloads (12 Months): 289, Citation Count: 124

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321694.321699 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	DINIC, E.A. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soy. Math. Dokl. 11 (1970), 1277-1280.
	2	EDMONDS, J. Paths, trees and flowers. Canadian J. Math. 17 (1965), 449 467.
	3	EDMONDS, J., AND KARP, R.M. Theoretical improvements in algorithmic efficiency for network flow problems. Combinatorial Structures and Their Applications. Gordon and Breach, New York, 1970, pp. 93-96 (abstract presented at Calgary International Conference on Combinatorial Structures and Their Applications, June 1969).
	4	EDMONDS, J., AND FULKERSON, D. R. Bottleneck extrema. RAND Corp. Memorandum RM-5375-PR (Jan. 1968).
	5	FORD, L. I{., AND FULKERSON, I). R. Flows in Networks. Princeton U. Press, Princeton, N.J., 1962.
	6	FULKERSON, D. ll. On the equivalence of the capacity-constrained transshipment problem and the Hitchcock problems. RAND Corp. Memorandum RM-2480 (Jan. 1960).
	7	WAGNER, H.M. On a class of capacitated transportation problems. Manag. Sci. 5 (1959), 304 318.

CITED BY 126

	Giuseppe Alia , Piero Maestrini, An approach to optimal partitioning of hypergraphs, Proceedings of the 1974 annual conference, p.133-139, January 1974
	Xiaotie Deng , Toshihide Ibaraki , Hiroshi Nagamochi, Combinatorial optimization games, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.720-729, January 05-07, 1997, New Orleans, Louisiana, United States
	Alon Itai, Two-Commodity Flow, Journal of the ACM (JACM), v.25 n.4, p.596-611, Oct. 1978
	To-Yat Cheung, Computational Comparison of Eight Methods for the Maximum Network Flow Problem, ACM Transactions on Mathematical Software (TOMS), v.6 n.1, p.1-16, March 1980
	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
	Steven L. Tanimoto , Alon Itai , Michael Rodeh, Some Matching Problems for Bipartite Graphs, Journal of the ACM (JACM), v.25 n.4, p.517-525, Oct. 1978
	B. Yang , H. Ural, Protocol conformance test generation using multiple UIO sequences with overlapping, ACM SIGCOMM Computer Communication Review, v.20 n.4, p.118-125, Sep. 1990
	J. Ian Munro , Pedro Celis, Techniques for collision resolution in hash tables with open addressing, Proceedings of 1986 ACM Fall joint computer conference, p.601-610, November 1986, Dallas, Texas, United States
	Takeshi Tokuyama , Jun Nakano, Efficient algorithms for the Hitchcock transportation problem, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.175-184, September 1992, Orlando, Florida, United States
	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977
	Edith Cohen , Nimrod Megiddo, Algorithms and complexity analysis for some flow problems, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.120-130, January 28-30, 1991, San Francisco, California, United States
	Harold N. Gabow, An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.448-456, December 1983
	Deborah C. Wang, Pad placement and ring routing for custom chip layout, Proceedings of the 27th ACM/IEEE conference on Design automation, p.193-199, June 24-27, 1990, Orlando, Florida, United States
	Bharat Kinariwala , A. G. Rao, Flow Switching Approach to the Maximum Flow Problem: I, Journal of the ACM (JACM), v.24 n.4, p.630-645, Oct. 1977
	Giuseppe Carenini , Raymond Ng , Xiaodong Zhou , Ed Zwart, Discovery and regeneration of hidden emails, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998
	Matthew Franklin , Zvi Galil , Moti Yung, Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, Journal of the ACM (JACM), v.47 n.2, p.225-243, March 2000
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate PCPs, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.41-50, May 01-04, 1999, Atlanta, Georgia, United States
	A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States
	Zvi Galil , Xiangdong Yu, Short length versions of Menger's theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.499-508, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.114-122, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Alon Efrat , Alon Itai, Improvements on bottleneck matching and related problems using geometry, Proceedings of the twelfth annual symposium on Computational geometry, p.301-310, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Sukumar Ghosh , Arobinda Gupta , Sriram V. Pemmaraju, A self-stabilizing algorithm for the maximum flow problem, Distributed Computing, v.10 n.4, p.167-180, July 1997
	D. S. Hochbaum , J. George Shanthikumar, Convex separable optimization is not much harder than linear optimization, Journal of the ACM (JACM), v.37 n.4, p.843-862, Oct. 1990
	Donald B. Johnson, A Note on Dijkstra's Shortest Path Algorithm, Journal of the ACM (JACM), v.20 n.3, p.385-388, July 1973
	David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States
	Thomas Ball , Peter Mataga , Mooly Sagiv, Edge profiling versus path profiling: the showdown, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.134-148, January 19-21, 1998, San Diego, California, United States
	S. B. Akers, On the use of the linear assignment algorithm in module placement, Papers on Twenty-five years of electronic design automation, p.218-223, June 1988
	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984
	Chi-Yuan Lo , Ravi Varadarajan, An O(n^1.5logn) 1-d compaction algorithm, Proceedings of the 27th ACM/IEEE conference on Design automation, p.382-387, June 24-27, 1990, Orlando, Florida, United States
	Sheldon B. Akers, On the use of the linear assignment algorithm in module placement, Proceedings of the 18th conference on Design automation, p.137-144, June 29-July 01, 1981, Nashville, Tennessee, United States
	Tetsuo Asano , Naoki Katoh , Koji Obokata , Takeshi Tokuyama, Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.896-904, January 06-08, 2002, San Francisco, California
	R. Endre Tarjan, Testing graph connectivity, Proceedings of the sixth annual ACM symposium on Theory of computing, p.185-193, April 30-May 02, 1974, Seattle, Washington, United States
	Samar Singh, Improved methods for storing and updating information in the out-of-kilter algorithm, Journal of the ACM (JACM), v.33 n.3, p.551-567, July 1986
	Tomasz Radzik , Andrew V. Goldberg, Tight bounds on the number of minimum-mean cycle cancellations and related results, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.110-119, January 28-30, 1991, San Francisco, California, United States
	Jens Vygen, On dual minimum cost flow algorithms (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.117-125, May 21-23, 2000, Portland, Oregon, United States
	Egon Balas , Donald Miller , Joseph Pekny , Paolo Toth, A parallel shortest augmenting path algorithm for the assignment problem, Journal of the ACM (JACM), v.38 n.4, p.985-1004, Oct. 1991
	Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States
	Satoru Iwata, A capacity scaling algorithm for convex cost submodular flows, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.482-489, January 28-30, 1996, Atlanta, Georgia, United States
	Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001
	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by canceling negative cycles, Journal of the ACM (JACM), v.36 n.4, p.873-886, Oct. 1989
	J. S. Mitchell, On maximum flows in polyhedral domains, Proceedings of the fourth annual symposium on Computational geometry, p.341-351, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States
	Zvi Galil , Éva Tardos, An O(n²(m + Nlog n)log n) min-cost flow algorithm, Journal of the ACM (JACM), v.35 n.2, p.374-386, April 1988
	Debaprosad Dutt , Chi-Yuan Lo, On minimal closure constraint generation for symbolic cell assembly, Proceedings of the 28th conference on ACM/IEEE design automation, p.736-739, June 17-22, 1991, San Francisco, California, United States
	Gaston Gonnet , Ian Munro, The analysis of an improved hashing technique, Proceedings of the ninth annual ACM symposium on Theory of computing, p.113-121, May 04-04, 1977, Boulder, Colorado, United States
	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987
	S. Thomas McCormick, A polynomial algorithm for abstract maximum flow, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.490-497, January 28-30, 1996, Atlanta, Georgia, United States
	Zvi Galil , Amnon Naamad, Network flow and generalized path compression, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.13-26, April 30-May 02, 1979, Atlanta, Georgia, United States
	Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.97-106, May 21-23, 2000, Portland, Oregon, United States
	Andreas S. Schulz , Robert Weismantel, The Complexity of Generic Primal Algorithms for Solving General Integer Programs, Mathematics of Operations Research, v.27 n.4, p.681-692, November 2002
	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988
	Christos D. Zaroliagis, Implementations and experimental studies of dynamic graph algorithms, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Navneet Malpani , Jianer Chen, A note on practical construction of maximum bandwidth paths, Information Processing Letters, v.83 n.3, p.175-180, 16 August 2002
	S. H. Bokhari, A Network Flow Model for Load Balancing in Circuit-Switched Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.649-657, June 1993
	Junehwa Song , G. Ramalingam , Raymond Miller , Byoung-Kee Yi, Interactive authoring of multimedia documents in a constraint-based authoring system, Multimedia Systems, v.7 n.5, p.424-437, September 1999
	Benno Schwikowski , Martin Vingron, Weighted sequence graphs: boosting iterated dynamic programming using locally suboptimal solutions, Discrete Applied Mathematics, v.127 n.1, p.95-117, April 2003
	Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Fully dynamic shortest paths in digraphs with arbitrary arc weights, Journal of Algorithms, v.49 n.1, p.86-113, 1 October 2003
	Rudolf Fleischer , Mordecai Golin , Chin-Tau Lea , Steven Wong, Finding optimal paths in MREP routing, Information Processing Letters, v.89 n.2, p.57-63, 31 January 2004
	Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate probabilistically checkable proofs, Information and Computation, v.189 n.2, p.135-159, March 15, 2004
	A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States
	Harold N. Gablow , Robert E. Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM (JACM), v.38 n.4, p.815-853, Oct. 1991
	Mark J. Eisner , Dennis G. Severance, Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases, Journal of the ACM (JACM), v.23 n.4, p.619-635, Oct. 1976
	Satoru Iwata , S. Thomas McCormick , Maiko Shigeno, A faster algorithm for minimum cost submodular flows, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.167-174, January 25-27, 1998, San Francisco, California, United States
	Y.-Q. Cheng , X. G. Wang , R. T. Collins , E. M. Riseman , A. R. Hanson, Three-Dimensional Reconstruction of Points and Lines with Unknown Correspondence across Images, International Journal of Computer Vision, v.45 n.2, p.129-156, November 2001
	Alan Holland , Barry O'Sullivan, Towards Fast Vickrey Pricing using Constraint Programming, Artificial Intelligence Review, v.21 n.3-4, p.335-352, June 2004
	Adam L. Buchsbaum , Raffaele Giancarlo, Algorithmic aspects in speech recognition: an introduction, Journal of Experimental Algorithmics (JEA), 2, p.1-es, 1997
	Cheol-Hoon Lee , Dongmyun Lee , Myunghwan Kim, Optimal Task Assignment in Linear Array Networks, IEEE Transactions on Computers, v.41 n.7, p.877-880, July 1992
	S. H. Bokhari, Partitioning Problems in Parallel, Pipeline, and Distributed Computing, IEEE Transactions on Computers, v.37 n.1, p.48-57, January 1988
	Pascal Ferraro , Christophe Godin, Optimal mappings with minimum number of connected components in tree-to-tree comparison problems, Journal of Algorithms, v.48 n.2, p.385-406, September 2003
	Whoi-Yul Kim , Avinash C. Kak, 3-D Object Recognition Using Bipartite Matching Embedded in Discrete Relaxation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.224-251, March 1991
	Troy A. Johnson , Rudolf Eigenmann , T. N. Vijaykumar, Min-cut program decomposition for thread-level speculation, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Sylvia C. Boyd , Hasan Ural, On the Complexity of Generating Optimal Test Sequences, IEEE Transactions on Software Engineering, v.17 n.9, p.976-978, September 1991
	Deming Chen , Jason Cong, Register binding and port assignment for multiplexer optimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.68-73, January 27-30, 2004, Yokohama, Japan
	Mrinmoy Hota , Madhumangal Pal , Tapan K. Pal, An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs, Computational Optimization and Applications, v.18 n.1, p.49-62, Jan. 2001
	Mattias Andersson , Joachim Gudmundsson , Christos Levcopoulos, Chips on wafers, or packing rectangles into grids, Computational Geometry: Theory and Applications, v.30 n.2, p.95-111, February 2005
	Panagiotis Papadimitratos , Zygmunt J. Haas , Emin Gün Sirer, Path set selection in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland
	Cheol-Hoon Lee , Kang G. Shin, Optimal Task Assignment in Homogeneous Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.119-129, February 1997
	Antonio Sedeño-Noda , Carlos González-Martín , Sergio Alonso, A generalization of the scaling max-flow algorithm, Computers and Operations Research, v.31 n.13, p.2183-2198, November 2004
	R. Guha , Ravi Kumar , D. Sivakumar , Ravi Sundaram, Unweaving a web of documents, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Mateo Restrepo , David P. Williamson, A simple GAP-canceling algorithm for the generalized maximum flow problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.534-543, January 22-26, 2006, Miami, Florida
	Li Yang, Building connected neighborhood graphs for isometric data embedding, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Stanislav Angelov , Boulos Harb , Sampath Kannan , Li-San Wang, Weighted isotonic regression under the L₁ norm, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.783-791, January 22-26, 2006, Miami, Florida
	Li Yang, Building k-edge-connected neighborhood graph for distance-based data projection, Pattern Recognition Letters, v.26 n.13, p.2015-2021, 1 October 2005
	Endre Boros , Peter L. Hammer , Ron Shamir, A Polynomial Algorithm for Balancing Acyclic Data Flow Graphs, IEEE Transactions on Computers, v.41 n.11, p.1380-1385, November 1992
	J.-Y. Juang , B. W. Wah, Resource Sharing Interconnection Networks in Multiprocessors, IEEE Transactions on Computers, v.38 n.1, p.115-129, January 1989
	Karen Aardal , Robert Weismantel , Laurence A. Wolsey, Non-standard approaches to integer programming, Discrete Applied Mathematics, v.123 n.1-3, p.5-74, 15 November 2002
	Robert Benkoczi , Hossam Hassanein , Selim Akl , Sylvia Tai, QoS for data relaying in hierarchical wireless sensor networks, Proceedings of the 1st ACM international workshop on Quality of service & security in wireless and mobile networks, October 13-13, 2005, Montreal, Quebec, Canada
	Sang-Young Cho, Geometrical k-cut problem and an optimal solution for hypercubes, Proceedings of the 12th WSEAS International Conference on Applied Mathematics, p.217-221, December 29-31, 2007, Cairo, Egypt
	R. Cerulli , M. Gentili , A. Iossa, Efficient preflow push algorithms, Computers and Operations Research, v.35 n.8, p.2694-2708, August, 2008
	Andrew Goldberg , Robert Tarjan, Finding minimum-cost circulations by canceling negative cycles, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.388-397, May 02-04, 1988, Chicago, Illinois, United States
	Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States
	David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996
	James Orlin, A faster strongly polynomial minimum cost flow algorithm, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.377-387, May 02-04, 1988, Chicago, Illinois, United States
	R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.22-32, May 06-08, 1985, Providence, Rhode Island, United States
	Eric H. Weigle , Andrew A. Chien, Partial content distribution on high performance networks, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA
	Li Yang, Data embedding techniques and applications, Proceedings of the 2nd international workshop on Computer vision meets databases, June 17-17, 2005, Baltimore, MD
	Mario Schkolnick, A survey of physical database design methodology and techniques, Proceedings of the fourth international conference on Very Large Data Bases, p.474-487, September 13-15, 1978, West Berlin, Germany
	Ron Y. Pinter , Oleg Rokhlenko , Dekel Tsur , Michal Ziv-Ukelson, Approximate labelled subtree homeomorphism, Journal of Discrete Algorithms, v.6 n.3, p.480-496, September, 2008
	Stefan Schäfer , Bernhard Scholz, Optimal chain rule placement for instruction selection based on SSA graphs, Proceedingsof the 10th international workshop on Software & compilers for embedded systems, April 20-20, 2007, Nice, France
	Wei-Chang Yeh, A simple Monte-Carlo method for estimating the continuous-state two-terminal network reliability at required demand level, Proceedings of the 2007 annual Conference on International Conference on Computer Engineering and Applications, p.164-170, January 17-19, 2007, Gold Coast, Queensland, Australia
	Jayant R. Kalagnanam , Andrew J. Davenport , Ho S. Lee, Computational Aspects of Clearing Continuous Call Double Auctions with Assignment Constraints and Indivisible Demand, Electronic Commerce Research, v.1 n.3, p.221-238, July 2001
	Uwe Naumann , Yuxiao Hu, Optimal vertex elimination in single-expression-use graphs, ACM Transactions on Mathematical Software (TOMS), v.35 n.1, p.1-20, July 2008
	Ying Liu , Alan P. Sprague, Outlier detection and evaluation by network flow, International Journal of Computer Applications in Technology, v.33 n.2/3, p.237-246, December 2008
	Minh Huynh , Prasant Mohapatra, Metropolitan Ethernet Network: A move from LAN to MAN, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.17, p.4867-4894, December, 2007
	Yinying Yang , Mihaela Cardei, Movement-assisted sensor redeployment scheme for network lifetime increase, Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, October 22-26, 2007, Chania, Crete Island, Greece
	Jianping Li , Lusheng Wang , Hao Zhao, On packing and coloring hyperedges in a cycle, Discrete Applied Mathematics, v.155 n.16, p.2140-2151, October, 2007
	Piotr Sankowski, Faster dynamic matchings and vertex connectivity, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.118-126, January 07-09, 2007, New Orleans, Louisiana
	Li Yang, Building k-Connected Neighborhood Graphs for Isometric Data Embedding, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.5, p.827-831, May 2006
	Konstantinos Paparrizos , Nikolaos Samaras , Angelo Sifaleras, An exterior simplex type algorithm for the Minimum Cost Network Flow Problem, Computers and Operations Research, v.36 n.4, p.1176-1190, April, 2009
	Aleksey Golovinskiy , Thomas Funkhouser, Randomized cuts for 3D mesh analysis, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
	Glencora Borradaile , Philip Klein, An O(n log n) algorithm for maximum st-flow in a directed planar graph, Journal of the ACM (JACM), v.56 n.2, p.1-30, April 2009
	J. Salez , D. Shah, Optimality of belief propagation for random assignment problem, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.187-196, January 04-06, 2009, New York, New York
	Vahid Tabatabaee , Leandros Tassiulas, MNCM: a critical node matching approach to scheduling for input buffered switches with no speedup, IEEE/ACM Transactions on Networking (TON), v.17 n.1, p.294-304, February 2009
	Abraham P. Punnen , Ruonan Zhang, Bottleneck flows in unit capacity networks, Information Processing Letters, v.109 n.6, p.334-338, February, 2009
	S. D. Pogorilyy , Yu. V. Boyko , A. D. Gusarov , S. I. Lozytskyi, An approach to the parallel solution of a high-dimensional basic flow problem, Cybernetics and Systems Analysis, v.45 n.2, p.291-296, March 2009
	Kenjiro Takazawa, A Weighted kt, t-Free t-Factor Algorithm for Bipartite Graphs, Mathematics of Operations Research, v.34 n.2, p.351-362, May 2009
	Justin Salez , Devavrat Shah, Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem, Mathematics of Operations Research, v.34 n.2, p.468-480, May 2009
	D. Benyamina , N. Hallam, Multi-criteria optimization approach for the deployment planning problem of multi-hop wireless networks, Proceedings of the international conference on Computational and information science 2009, p.454-460, April 30-May 02, 2009, Houston, USA
	Sang-Young Cho , Hee-Chul Kim, An optimal algorithm for tree geometrical k-cut problem, Proceedings of the 10th WSEAS international conference on Mathematical and computational methods in science and engineering, p.280-285, November 07-09, 2008, Bucharest, Romania
	Chun Hau Lau , Boon-Hee Soong , S. K. Bose, Path selection with preemption and re-routing control for multi-protocol label switching networks, Computer Communications, v.29 n.18, p.3718-3732, November, 2006
	Peter Van Beek, Approximation algorithms for temporal reasoning, Proceedings of the 11th international joint conference on Artificial intelligence, p.1291-1296, August 20-25, 1989, Detroit, Michigan
	Roberto Navigli , Mirella Lapata, Graph connectivity measures for unsupervised word sense disambiguation, Proceedings of the 20th international joint conference on Artifical intelligence, p.1683-1688, January 06-12, 2007, Hyderabad, India
	Mark Hoogendoorn, Adaptation of organizational models for multi-agent systems based on max flow networks, Proceedings of the 20th international joint conference on Artifical intelligence, p.1321-1326, January 06-12, 2007, Hyderabad, India
	J. Dauwels , F. Vialatte , T. Weber , T. Musha , A. Cichocki, Quantifying statistical interdependence by message passing on graphs---part ii: Multidimensional point processes, Neural Computation, v.21 n.8, p.2203-2268, August 2009