Sequence Hypergraphs

详细信息    查看全文

• 关键词：Colored graphs ; Labeled problems ; Oriented hypergraphs ; Algorithms ; Complexity
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9941
• 期：1
• 页码：282-294
• 全文大小：290 KB
• 参考文献：1.Ausiello, G., Franciosa, P.G., 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. 2202, p. 312. Springer, Heidelberg (2001)CrossRef
  2.Ausiello, G., Giaccio, R., Italiano, G.F., Nanni, U.: Optimal traversal of directed hypergraphs. Technical report (1992)
  3.Barbut, E., Bialostocki, A.: A generalization of rotational tournaments. Discrete Math. 76(2), 81–87 (1989)MathSciNet CrossRef MATH
  4.Berry, J., Dean, N., Goldberg, M., Shannon, G., Skiena, S.: Graph drawing and manipulation with link. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 425–437. Springer, Heidelberg (1997)CrossRef
  5.Böhmová, K., Mihalák, M., Pröger, T., Sacomoto, G., Sagot, M.-F.: Computing and listing st-paths in public transportation networks. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 102–116. Springer, Heidelberg (2016). doi:10.​1007/​978-3-319-34171-2_​8 CrossRef
  6.Broersma, H., Li, X., Woeginger, G., Zhang, S.: Paths and cycles in colored graphs. Australas. J. Comb. 31, 299–311 (2005)MathSciNet MATH
  7.Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.V.: On the red-blue set cover problem. In: SODA 2000. vol. 9, pp. 345–353. Citeseer (2000)
  8.Coudert, D., Datta, P., Pérennes, S., Rivano, H., Voge, M.E.: Shared risk resource group complexity and approximability issues. Parallel Process. Lett. 17(02), 169–184 (2007)MathSciNet CrossRef
  9.Coudert, D., Pérennes, S., Rivano, H., Voge, M.E.: Combinatorial optimization in networks with Shared Risk Link Groups. Research report, INRIA, October 2015
  10.Elias, P., Feinstein, A., Shannon, C.E.: A note on the maximum flow through a network. IRE Trans. Inf. Theor. 2(4), 117–119 (1956)CrossRef
  11.Erdős, P.L., Frankl, P., Katona, G.O.: Intersecting sperner families and their convex hulls. Combinatorica 4(1), 21–34 (1984)MathSciNet CrossRef MATH
  12.Fellows, M.R., Guo, J., Kanj, I.A.: The parameterized complexity of some minimum label problems. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 88–99. Springer, Heidelberg (2010)CrossRef
  13.Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2), 177–201 (1993)MathSciNet CrossRef MATH
  14.Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)MATH
  15.Goldberg, P.W., McCabe, A.: Shortest paths with bundles and non-additive weights is hard. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 264–275. Springer, Heidelberg (2013)CrossRef
  16.Gutin, G., Yeo, A.: Hamiltonian paths and cycles in hypertournaments. J. Graph Theor. 25(4), 277–286 (1997)MathSciNet CrossRef MATH
  17.Hassin, R., Monnot, J., Segev, D.: Approximation algorithms and hardness results for labeled connectivity problems. J. Comb. Opt. 14(4), 437–453 (2007)MathSciNet CrossRef MATH
  18.Hu, J.Q.: Diverse routing in optical mesh networks. IEEE Trans. Commun. 51(3), 489–494 (2003)CrossRef
  19.Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335–349 (2008)MathSciNet CrossRef MATH
  20.Krumke, S.O., Wirth, H.C.: On the minimum label spanning tree problem. Inf. Process. Lett. 66(2), 81–85 (1998)MathSciNet CrossRef MATH
  21.Wachman, G., Khardon, R.: Learning from interpretations: a rooted kernel for ordered hypergraphs. In: Proceedings of the 24th International Conference on Machine Learning, pp. 943–950. ACM (2007)
  22.Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. In: INFOCOM 2005, vol. 4, pp. 2658–2669. IEEE (2005)
  23.Zhang, P., Cai, J.Y., Tang, L.Q., Zhao, W.B.: Approximation and hardness results for label cut and related problems. J. Comb. Opt. 21(2), 192–208 (2011)MathSciNet CrossRef MATH
  
• 作者单位：Kateřina Böhmová (14)
  Jérémie Chalopin (15)
  Matúš Mihalák (14) (16)
  Guido Proietti (17) (18)
  Peter Widmayer (14)
  
  14. Institute of Theoretical Computer Science, ETH Zürich, Zürich, Switzerland
  15. LIF, CNRS & Aix-Marseille University, Marseille, France
  16. Department of Knowledge Engineering, Maastricht University, Maastricht, The Netherlands
  17. DISIM, Università degli Studi dell’Aquila, L’Aquila, Italy
  18. IASI, CNR, Roma, Italy
  
• 丛书名：Graph-Theoretic Concepts in Computer Science
• ISBN：978-3-662-53536-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9941

文摘

We introduce sequence hypergraphs by extending the concept of a directed edge (from simple directed graphs) to hypergraphs. Specifically, every hyperedge of a sequence hypergraph is defined as a sequence of vertices (imagine it as a directed path). Note that this differs substantially from the standard definition of directed hypergraphs. Sequence hypergraphs are motivated by problems in public transportation networks, as they conveniently represent transportation lines. We study the complexity of some classic algorithmic problems, arising (not only) in transportation, in the setting of sequence hypergraphs. In particular, we consider the problem of finding a shortest st-hyperpath: a minimum set of hyperedges that “connects” (allows to travel to) t from s; finding a minimum st-hypercut: a minimum set of hyperedges whose removal “disconnects” t from s; or finding a maximum st-hyperflow: a maximum number of hyperedge-disjoint st-hyperpaths.