{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:58:00Z","timestamp":1760245080181},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_40","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"481-493","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Linear Connectivity Problems in Directed Hypergraphs"],"prefix":"10.1007","author":[{"given":"Mayur","family":"Thakur","sequence":"first","affiliation":[]},{"given":"Rahul","family":"Tripathi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0012-365X(79)90103-1","volume":"27","author":"B. Acharya","year":"1979","unstructured":"Acharya, B.: On the cyclomatic number of a hypergraph. Discrete Mathematics\u00a027, 111\u2013116 (1979)","journal-title":"Discrete Mathematics"},{"key":"40_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0023812","volume-title":"LATIN \u201992","author":"P. Alimonti","year":"1992","unstructured":"Alimonti, P., Feuerstein, E., Nanni, U.: Linear time algorithms for liveness and boundedness in conflict-free Petri nets. In: Simon, I. (ed.) LATIN 1992. LNCS, vol.\u00a0583, pp. 1\u201314. Springer, Heidelberg (1992)"},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1145\/2157.322404","volume":"30","author":"G. Ausiello","year":"1983","unstructured":"Ausiello, G., D\u2019Atri, A., Sacc\u00e1, D.: Graph algorithms for functional dependency manipulation. Journal of the ACM\u00a030, 752\u2013766 (1983)","journal-title":"Journal of the ACM"},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0215029","volume":"15","author":"G. Ausiello","year":"1986","unstructured":"Ausiello, G., D\u2019Atri, A., Sacc\u00e1, D.: Minimal representation of directed hypergraphs. SIAM Journal on Computing\u00a015, 418\u2013431 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"40_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/3-540-45446-2_20","volume-title":"Theoretical Computer Science","author":"G. Ausiello","year":"2001","unstructured":"Ausiello, G., Franciosa, P., Frigioni, D.: Directed hypergraphs: Problems, algorithmic results, and a novel decremental approach. In: Restivo, A., Ronchi Della Rocca, S., Roversi, L. (eds.) ICTCS 2001. LNCS, vol.\u00a02202, pp. 312\u2013328. Springer, Heidelberg (2001)"},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(96)00123-5","volume":"171","author":"G. Ausiello","year":"1997","unstructured":"Ausiello, G., Giaccio, R.: On-line algorithms for satisfiability formulae with uncertainty. Theoretical Computer Science\u00a0171, 3\u201324 (1997)","journal-title":"Theoretical Computer Science"},{"key":"40_CR7","unstructured":"Ausiello, G., Giaccio, R., Italiano, G., Nanni, U.: Optimal traversal of directed hypergraphs (Manuscript 1997)"},{"key":"40_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0055754","volume-title":"Mathematical Foundations of Computer Science 1998","author":"G. Ausiello","year":"1998","unstructured":"Ausiello, G., Italiano, G., Nanni, U.: Hypergraph traversal revisited: Cost measures and dynamic algorithms. In: Brim, L., Gruska, J., Zlatu\u0161ka, J. (eds.) MFCS 1998. LNCS, vol.\u00a01450, pp. 1\u201316. Springer, Heidelberg (1998)"},{"key":"40_CR9","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973)"},{"key":"40_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G. Gallo","year":"1993","unstructured":"Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Applied Mathematics\u00a042, 177\u2013201 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"40_CR11","unstructured":"Gallo, G., Rago, G.: A hypergraph approach to logical inference for datalog formulae. Technical Report 28\/90, Dip.\u00a0di Informatica, Univ.\u00a0of Pisa, Italy (1990)"},{"key":"40_CR12","unstructured":"Gallo, G., Scutella, M.: Directed hypergraphs as a modelling paradigm. Technical Report TR-99-02, Dipartimento di Informatica (February 1999)"},{"issue":"3","key":"40_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Information and Control\u00a056(3), 183\u2013198 (1983)","journal-title":"Information and Control"},{"key":"40_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"40_CR15","first-page":"335","volume-title":"3rd Italian Conf. on Theoretical Computer Science","author":"G. Italiano","year":"1989","unstructured":"Italiano, G., Nanni, U.: On line maintainenance of minimal directed hypergraphs. In: 3rd Italian Conf. on Theoretical Computer Science, pp. 335\u2013349. World Scientific Co., Singapore (1989)"},{"key":"40_CR16","unstructured":"Klein, D., Manning, C.: Parsing and hypergraphs. In: Proceedings of the 7th International Workshop on Parsing Technologies, IWPT 2001(2001)"},{"issue":"1","key":"40_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(77)90002-3","volume":"6","author":"D. Knuth","year":"1977","unstructured":"Knuth, D.: A generalization of Dijkstra\u2019s algorithm. Information Processing Letters\u00a06(1), 1\u20135 (1977)","journal-title":"Information Processing Letters"},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/BFb0083470","volume":"1403","author":"S. Nguyen","year":"1989","unstructured":"Nguyen, S., Pallottino, S.: Hyperpaths and shortest hyperpaths. Combinatorial Optimization\u00a01403, 258\u2013271 (1989)","journal-title":"Combinatorial Optimization"},{"key":"40_CR19","unstructured":"Nielsen, L., Pretolani, D., Andersen, K.: A remark on the definition of a B-hyperpath. Technical report, Department of Operations Research, University of Aarhus (2001)"},{"key":"40_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-09438-9","volume-title":"Principles of Artificial Intelligence","author":"N. Nilson","year":"1982","unstructured":"Nilson, N.: Principles of Artificial Intelligence. Springer, Heidelberg (1982)"},{"key":"40_CR21","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"3","key":"40_CR22","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C. Papadimitriou","year":"1986","unstructured":"Papadimitriou, C., Yannakakis, M.: A note on succinct representations of graphs. Information and Control\u00a071(3), 181\u2013185 (1986)","journal-title":"Information and Control"},{"key":"40_CR23","unstructured":"Petri, C.: Communication with automata. Technical Report Supplement 1 to Tech.\u00a0Report RADC-TR-65-377,1, Univ.\u00a0of Bonn (1962)"},{"key":"40_CR24","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the Shortest Path problem. Journal of Algorithms\u00a021, 267\u2013305 (1996)","journal-title":"Journal of Algorithms"},{"key":"40_CR25","unstructured":"Tantau, T.: A note on the complexity of the reachability problem for tournaments. In: ECCCTR: Electronic Colloquium on Computational Complexity (2001)"},{"key":"40_CR26","volume-title":"Chemical Reaction Networks: A Graph-Theoretical Approach","author":"O. Temkin","year":"1996","unstructured":"Temkin, O., Zeigarnik, A., Bonchev, D.: Chemical Reaction Networks: A Graph-Theoretical Approach. CRC Press, Boca Raton (1996)"},{"key":"40_CR27","unstructured":"Thakur, M., Tripathi, R.: Complexity of linear connectivity problems in directed hypergraphs. Technical Report TR814, Department of Computer Science, University of Rochester (September 2003)"},{"key":"40_CR28","unstructured":"Ullman, J.: Principles of Database Systems. Computer Science Press (1982)"},{"key":"40_CR29","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. Wagner","year":"1986","unstructured":"Wagner, K.: The complexity of combinatorial problems with succinct input representations. Acta Informatica\u00a023, 325\u2013356 (1986)","journal-title":"Acta Informatica"},{"key":"40_CR30","unstructured":"Zeigarnik, A.: On hypercycles and hypercircuits in hypergraphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a051 (2000)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:58:56Z","timestamp":1605761936000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}