{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:49:09Z","timestamp":1767340149692},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1988,11,1]],"date-time":"1988-11-01T00:00:00Z","timestamp":594345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1988,11]]},"DOI":"10.1007\/bf01762131","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:22:38Z","timestamp":1118917358000},"page":"549-560","source":"Crossref","is-referenced-by-count":12,"title":["On finding optimal and near-optimal lineal spanning trees"],"prefix":"10.1007","volume":"3","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donald K.","family":"Friesen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Langston","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01762131_CR1","doi-asserted-by":"crossref","unstructured":"R. Anderson, A Parallel Algorithm for the Maximal Path Problem,Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (1985), 33\u201337.","DOI":"10.1145\/22145.22149"},{"key":"BF01762131_CR2","unstructured":"E. C. Freuder and M. J. Quinn, Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems,Proceedings of the Ninth International Joint Conference on Artificial Intelligence (1985), 1076\u20131078."},{"key":"BF01762131_CR3","unstructured":"E. C. Freuder and M. J. Quinn, Parallelism in an Algorithm that Takes Advantage of Stable Sets of Variables to Solve Constraint Satisfaction Problems, Computer Science Technical Report, University of New Hampshire, 1985."},{"key":"BF01762131_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"BF01762131_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","volume":"14","author":"R. M. Haralick","year":"1980","unstructured":"R. M. Haralick and G. L. Elliot, Increasing Tree Search Efficiency for Constraint Satisfaction Problems,Artificial Intelligence 14 (1980), 263\u2013313.","journal-title":"Artificial Intelligence"},{"key":"BF01762131_CR6","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"J. Hopcroft, and R. Tarjan, Efficient Planarity Testing,Journal of the Association for Computing Machinery 21 (1974), 549\u2013568.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01762131_CR7","volume-title":"Logic for Problem Solving","author":"R. Kowalski","year":"1979","unstructured":"R. Kowalski,Logic for Problem Solving, North Holland, Amsterdam, 1979."},{"key":"BF01762131_CR8","first-page":"597","volume":"29","author":"P. C. Liu","year":"1980","unstructured":"P. C. Liu and R. C. Geldmacher, An O(max(m, n)) Algorithm for Finding a Subgraph Homeomorphic to K4,Congressus Numerantium 29 (1980), 597\u2013609.","journal-title":"Congressus Numerantium"},{"key":"BF01762131_CR9","unstructured":"A. Mackworth, Constraint Satisfaction, Computer Science Technical Report, University of British Columbia, 1985."},{"key":"BF01762131_CR10","unstructured":"B. A. Nadel, Theory-Based Search-Order Selection for Constraint Satisfaction Problems, Computer Science Technical Report, University of Michigan, 1986."},{"key":"BF01762131_CR11","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C. H. Papadimitriou","year":"1982","unstructured":"C. H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"BF01762131_CR12","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1137\/0215058","volume":"15","author":"J. R. Smith","year":"1986","unstructured":"J. R. Smith, Parallel Algorithms for Depth-First Searches I. Planar Graphs,SIAM Journal on Computing 15 (1986), 814\u2013830.","journal-title":"SIAM Journal on Computing"},{"key":"BF01762131_CR13","volume-title":"Graphs, Networks, and Algorithms","author":"M. N. S. Swany","year":"1981","unstructured":"M. N. S. Swany and K. Thulasiraman,Graphs, Networks, and Algorithms, Wiley, New York, 1981."},{"key":"BF01762131_CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0196-6774(86)90040-4","volume":"7","author":"P. Tiwari","year":"1986","unstructured":"P. Tiwari, An Efficient Parallel Algorithm for Shifting the Root of a Depth-First Spanning Tree,Journal of Algorithms 7 (1986), 105\u2013119.","journal-title":"Journal of Algorithms"},{"key":"BF01762131_CR15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1080\/03081088308817513","volume":"13","author":"K. P. Vo","year":"1983","unstructured":"K. P. Vo, Finding Triconnected Components of Graphs,Linear and Multilinear Algebra 13 (1983), 143\u2013165.","journal-title":"Linear and Multilinear Algebra"},{"key":"BF01762131_CR16","volume-title":"Combinatorics for Computer Science","author":"S. G. Williamson","year":"1985","unstructured":"S. G. Williamson,Combinatorics for Computer Science, Computer Science Press, Rockville, MD, 1985."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762131.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01762131\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T16:41:43Z","timestamp":1557333703000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01762131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,11]]},"references-count":16,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1988,11]]}},"alternative-id":["BF01762131"],"URL":"https:\/\/doi.org\/10.1007\/bf01762131","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,11]]}}}