The network inhibition problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The network inhibition problem

Full text

Pdf (1.19 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 776 - 785

Year of Publication: 1993

ISBN:0-89791-591-7

Author

Cynthia A. Phillips

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 99, Citation Count: 12

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/167088.167286 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	Alok Aggarwal , Maria Klawe, Applications of generalized matrix searching to geometric algorithms, Discrete Applied Mathematics, v.27 n.1-2, p.3-23, May 1990 [doi>10.1016/0166-218X(90)90124-U]
	2	A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber, "Geometric applications of a matrixsearching algorithm", Algorithmica, 2(2):195-208, 1987.
	3	Alok Aggarwal , James K. Park, Improved algorithms for economic lot size problems, Operations Research, v.41 n.3, p.549-571, May/June 1993 [doi>10.1287/opre.41.3.549]
	4	M. O. Ball and j. S. Provan, "Calculating bounds on teachability and connectedness in stochastic networks", Networks, 13:253-278, 1983.
	5	Dan Bienstock, Some generalized max-flow min-cut problems in the plane, Mathematics of Operations Research, v.16 n.2, p.310-333, May 1991 [doi>10.1287/moor.16.2.310]
	6	P. Z. Chinn, :I. Chv~talov~, A. K. Dewdney, N.E. Gibbs, "The bandwidth problem for graphs and matrices a survey", J. Graph Theory, Vol. 6, 1982, pp. 223-254.
	7	J. Chv~talov~, A. K. Dewdney, N. E. Gibbs, R. R. Korfhage, "The bandwidth problem for graphs: a collection of recent results", Res. report #24, Dept. of Comput. Sci., UWO, London, Ont, 1975.
	8	Joseph Cheriyan , Torben Hagerup , Kurt Mehlhorn, Can a maximum flow be computed in o(nm) time?, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.235-248, July 1990, Warwick University, England
	9	William H. Cunningham, Optimal attack and reinforcement of a network, Journal of the ACM (JACM), v.32 n.3, p.549-561, July 1985 [doi>10.1145/3828.3829]
	10	L. R. Ford Jr. and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, Princeton, Nil, 1962.
	11	Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
	12	Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991 [doi>10.1145/102782.102788]
	13	G. Gallo , M. D. Grigoriadis , R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM Journal on Computing, v.18 n.1, p.30-55, Feb. 1989 [doi>10.1137/0218003]
	14	M. R. Garey, D. S. Johnson, and L. Stockmeyer, "Some simplified NP-complete graph problems", Theoretical Computer Science, 1:237-267, 1976.
	15	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	16	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 [doi>10.1145/48014.61051]
	17	O. Goldschmidt and D. Hochbaum, "Polynomial algorithm for the k-cut problem", Proc. 29th FOCS, 1988, pp. 444-451.
	18	Dan Gusfield, Computing the strength of a graph, SIAM Journal on Computing, v.20 n.4, p.639-654, Aug. 1991 [doi>10.1137/0220040]
	19	F. Hadlock, "Finding a maximum cut of a planar graph in polynomial time", SIAM J. Comput., 4(3):221-225, Sept. 1975.
	20	Peter L. Hammer , Frédéric Maffray , Maurice Queyranne, Cut-threshold graphs, Discrete Applied Mathematics, v.30 n.2-3, p.163-179, Feb. 28, 1991
	21	F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1972.
	22	Refael Hassin, Approximation schemes for the restricted shortest path problem, Mathematics of Operations Research, v.17 n.1, p.36-42, Feb. 1992 [doi>10.1287/moor.17.1.36]
	23	R. Hassin and D. Johnson, "An O(nlog2 n) algorithm for maximum flow in undirected planar networks", SIAM J. Comput., 14(3):612-624, Aug. 1985.
	24	A. Itai and Y. Shiloach, "Maximum flow in planar networks", SIAM J. Compute., 8(2):135-150, 1979.
	25	D. Johnson, "The NP-completeness column: an ongoing guide (16th)", J. Alg., 6(3):434-451, 1985.
	26	H. C. :Ioksch, "The shortest route problem with Constraints", J. Math. Anal. Appl., 14:191-197, 1966.
	27	R. Karp, "Reducibility among combinatorial problems", in Complexzty of Computer Computaiions, R. E. Miller and J. W. Thatcher eds., Plenum Press, NY, 1972, pp. 85-103.
	28	V. King , S. Rao , R. Tarjan, A faster deterministic maximum flow algorithm, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.157-164, September 1992, Orlando, Florida, United States
	29	Maria M. Klawe , Daniel J. Kleitman, An almost linear time algorithm for generalized matrix searching, SIAM Journal on Discrete Mathematics, v.3 n.1, p.81-97, Feb. 1990 [doi>10.1137/0403009]
	30	P.N. Klein, A. Agrawal, R. Ravi, and S. Rao, "Approximation through multicommodity flow," Proc. 31s# Annual FOCS, 1990, pp. 726-737.
	31	E. L. Lawler, Combinatorial Optimizalzon: Networks and Matroids, Holt, Rinehart, and Winston, New York, 1976.
	32	E. Minieka, "Maximal, lexicographic, and dynamic network flows", Oper. _Res., 21(2):517-527, 1973.
	33	J. K. Park and C. A. Phillips, manuscript in preparation.
	34	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	35	C. A. Phillips, manuscript in preparation.
	36	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	37	J. S. Provan and M. O. Ball, "The complexity of counting cuts and of computing the probability that a graph is connected", SIAM J. Compul., 12(4):777-788, Nov. 1983.
	38	J. Reif, "Minimum s-t cut of a planar undirected network in O(nlog2(n)) time", SIAM J. Comput., 12(1):71-81, Feb. 1983.
	39	I#va Tardos, priviate communication.
	40	S. Tsukiyama , I. Shirakawa , H. Ozaki , H. Ariyoshi, An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset, Journal of the ACM (JACM), v.27 n.4, p.619-632, Oct. 1980 [doi>10.1145/322217.322220]

CITED BY 12

	Cynthia Phillips , Laura Painton Swiler, A graph-based system for network-vulnerability analysis, Proceedings of the 1998 workshop on New security paradigms, p.71-79, September 22-26, 1998, Charlottesville, Virginia, United States
	Greg N. Frederickson , Roberto Solis-Oba, Efficient algorithms for robustness in matroid optimization, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.659-668, January 05-07, 1997, New Orleans, Louisiana, United States
	Funda Ergun , Rakesh Sinha , Lisa Zhang, An improved FPTAS for restricted shortest path, Information Processing Letters, v.83 n.5, p.287-291, 15 September 2002
	H. Noltemeier , H.-C. Wirth , S. O. Krumke, Network design and improvement, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	Patrick Briest , Piotr Krysta , Berthold Vöcking, Approximation techniques for utilitarian mechanism design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	G. Calinescu , S. Kapoor , M. Sarwat, Bounded-hops power assignment in ad hoc wireless networks, Discrete Applied Mathematics, v.154 n.9, p.1358-1371, 1 June 2006
	Greg N. Frederickson , Roberto Solis-Oba, Efficient algorithms for robustness in resource allocation and scheduling problems, Theoretical Computer Science, v.352 n.1, p.250-265, 7 March 2006
	Ran Giladi , Ephraim Korach , Rony Ohayon, Path selection under multiple QoS constraints - a practical approach, Journal of High Speed Networks, v.13 n.2, p.155-167, April 2004
	Greg N. Frederickson , Roberto Solis-Oba, Increasing the weight of minimum spanning trees, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.539-546, January 28-30, 1996, Atlanta, Georgia, United States
	Gerald Brown , Matthew Carlyle , Douglas Diehl , Jeffrey Kline , Kevin Wood, A Two-Sided Optimization for Theater Ballistic Missile Defense, Operations Research, v.53 n.5, p.745-763, September-October 2005
	Harald Held , David L. Woodruff, Heuristics for Multi-Stage Interdiction of Stochastic Networks, Journal of Heuristics, v.11 n.5-6, p.483-500, December 2005
	Christoph Albrecht , Andrew B. Kahng , Ion Mandoiu , Alexander Zelikovsky, Floorplan Evaluation with Timing-Driven Global Wireplanning, Pin Assignment and Buffer/Wire Sizing, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.580, January 07-11, 2002