Beyond NP-completeness for problems of bounded width (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy

Full text

Pdf (1.17 MB)

Source

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

Montreal, Quebec, Canada

Pages: 449 - 458

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Hans L. Bodlaender	Department of Computer Science, Utrecht University, Padualaan 14, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands
Michael R. Fellows	Department of Computer Science, University of Victoria, P.O. Box 3055, Victoria, B.C. V8W 3P6, Canada
Michael T. Hallett	Department of Computer Science, University of Victoria, P.O. Box 3055, Victoria, B.C. V8W 3P6, Canada

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 33, Citation Count: 5

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/195058.195229 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	Karl R. Abrahamson , Rodney G. Downey , Michael R. Fellows, Fixed-Parameter Intractability II (Extended Abstract), Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.374-385, February 25-27, 1993
	2	K. Abrahamson, M. Fellows: Fiinite automata, bounded treewidth and well-quasiordering. Proceedings of the AMS Summer Workshop on Graph Minors (Seattle, 1991), A.M.S. Contemporary Mathematics Series vol. 147, Graph Structure Theory, eds. N. Robertson and P. Seymour (1993), 539-564.
	3	Stefan Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded, decomposability—a survey, BIT, v.25 n.1, p.2-23, 1985
	4	Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
	5	Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
	6	Hans L. Bodlaender, Dynamic Programming on Graphs with Bounded Treewidth, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.105-118, July 11-15, 1988
	7	Hans L. Bodlaender, The complexity of finding uniform emulations on paths and ring networks, Information and Computation, v.86 n.1, p.87-106, May 1990 [doi>10.1016/0890-5401(90)90027-F]
	8	Hans L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.226-234, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167161]
	9	Hans L. Bodlaender , Michael R. Fellows , Tandy Warnow, Two Strikes Against Perfect Phylogeny, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.273-283, July 13-17, 1992
	10	R. B. Boric, R. G. Parker, C. A. Tovey: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7 (1992), 555-582.
	11	L. Cat, J. Chen, R. Downey and M. Fellows: The parameterized complexity of short computations and factorizations. University of Victoria, Technical Report, Department of Computer Science, July, 1993.
	12	Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
	13	Rodney G. Downey , Patricia A. Evans , Michael R. Fellows, Parameterized learning complexity, Proceedings of the sixth annual conference on Computational learning theory, p.51-57, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168311]
	14	R. G. Downey, M. R. Fellows: Fixed parameter tractability and completeness. Congr. Num. 87 (1992), 161-187.
	15	Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
	16	Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995 [doi>10.1016/0304-3975(94)00097-3]
	17	R. G. Downey, M. R. Fellows: Fixed parameter intractability. Proceedings of lhe Seventh Annual IEEE Conference on Struclure in Complexity The- 0ry (1992), 36-49.
	18	Rod Downey , Michael Fellows, Fixed-parameter tractability and completeness III: some structural aspects of the W hierarchy, Complexity theory: current research, Cambridge University Press, New York, NY, 1993
	19	R. G. Downey and M. R. Fellows: Parameterized computational feasibility. To appear in Proc. Second Cornell Workshop on Feasible Mathematzcs (Birkhauser, Boston).
	20	R. G. Downey and M. R. Fellows: Parameterized complexity. Monograph in preparation.
	21	Michael T. Hallett , Harold T. Wareham, The Parameterized Complexity of Some Problems in Logic and Linguistics, Proceedings of the Third International Symposium on Logical Foundations of Computer Science, p.89-100, July 11-14, 1994
	22	Michael R. Fellows , Michael T. Hallett , Harold T. Wareham, DNA Physical Mapping: Three Ways Difficult, Proceedings of the First Annual European Symposium on Algorithms, p.157-168, September 30-October 02, 1993
	23	Michael R. Fellows , Neal Koblitz, Fixed-Parameter Complexity and Cryptography, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.121-131, May 10-14, 1993
	24	D. Fernández-Baca , A. Medepalli, Parametric Module Allocation on Partial k-Trees, IEEE Transactions on Computers, v.42 n.6, p.738-742, June 1993 [doi>10.1109/12.277293]
	25	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
	26	M. Golumbic, H. Kaplan, R. Shamir: On the complexity of DNA physical mapping. Technical Report 271/93, Tel Aviv University, January 1993, to appear in Adv. AppL Math.
	27	E. M. Gurari and I. H. Sudborough. Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem. J. Algorithms 5 (1984), 531-546.
	28	F. R. McMorris , Tandy J. Warnow , Thomas Wimer, Triangulating vertex colored graphs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.120-127, January 25-27, 1993, Austin, Texas, United States
	29	C. H. Papadimitriou and M. Yannakakis: On limited nondeterminism and the complexity of the V-C dimension. Proceedings of the 1993 IEEE Conf. on Structure in Complexity Theory, (1993), 12-18.
	30	D. P. Sanders: On linear recognition of tree-width at most four. Manuscript, Mathematics Department, Georgia Tech., November 1992.
	31	J. B. Saxe. Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Alg. Disc. Meth. 1 (1980), 363-369.
	32	Thomas Victor Wimer , Stephen T. Hedetniemi, Linear algorithms on k-terminal graphs, 1987

CITED BY 5

	Josep Díaz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002
	Uriel Feige, Approximating the bandwidth via volume respecting embeddings (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.90-99, May 24-26, 1998, Dallas, Texas, United States
	Rodney G. Downey , Catherine McCartin, Bounded persistence pathwidth, Proceedings of the 2005 Australasian symposium on Theory of computing, p.51-56, January 01, 2005, Newcastle, Australia
	Virginia Vassilevska , Ryan Williams , Shan Leung Maverick Woo, Confronting hardness using a hybrid approach, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1-10, January 22-26, 2006, Miami, Florida
	Rodney G. Downey , Catherine McCartin, Online promise problems with online width metrics, Journal of Computer and System Sciences, v.73 n.1, p.57-72, February, 2007