{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:46:12Z","timestamp":1740098772794,"version":"3.37.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319530062"},{"type":"electronic","value":"9783319530079"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-53007-9_26","type":"book-chapter","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T05:13:23Z","timestamp":1486012403000},"page":"294-307","source":"Crossref","is-referenced-by-count":0,"title":["The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Abdullah","family":"Makkeh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mozhgan","family":"Pourmoradnasseri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk Oliver","family":"Theis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,26]]},"reference":[{"key":"26_CR1","unstructured":"Aguilera, N., Katz, R., Tolomei, P.: Vertex adjacencies in the set covering polyhedron. arXiv preprint arXiv:1406.6015 (2014)"},{"key":"26_CR2","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1016\/j.disc.2005.11.030","volume":"306","author":"TS Arthanari","year":"2006","unstructured":"Arthanari, T.S.: On pedigree polytopes and hamiltonian cycles. Discret. Math. 306, 1474\u20131792 (2006)","journal-title":"Discret. Math."},{"issue":"3","key":"26_CR3","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/j.disopt.2013.07.001","volume":"10","author":"TS Arthanari","year":"2013","unstructured":"Arthanari, T.S.: Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope. Discret. Optim. 10(3), 224\u2013232 (2013). http:\/\/dx.doi.org\/10.1016\/j.disopt.2013.07.001","journal-title":"Discret. Optim."},{"issue":"3","key":"26_CR4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0166-218X(99)00154-7","volume":"98","author":"TS Arthanari","year":"2000","unstructured":"Arthanari, T.S., Usha, M.: An alternate formulation of the symmetric traveling salesman problem and its properties. Discret. Appl. Math. 98(3), 173\u2013190 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"26_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.disc.2012.09.015","volume":"313","author":"S Fiorini","year":"2013","unstructured":"Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.O.: Combinatorial bounds on nonnegative rank and extended formulations. Discret. Math. 313(1), 67\u201383 (2013)","journal-title":"Discret. Math."},{"key":"26_CR6","unstructured":"Gr\u00f6tschel, M., Padberg, M.W.: Polyhedral theory. In: Lawler, E.L., Lenstra, J.K., Kan, A., Shmoys, D.B. (eds.) The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, chap. 8, pp. 251\u2013306. Wiley (1985)"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-540-25960-2_30","volume-title":"Integer Programming and Combinatorial Optimization","author":"V Kaibel","year":"2004","unstructured":"Kaibel, V.: Low-dimensional faces of random 0\/1-polytopes. In: Bienstock, D., Nemhauser, G. (eds.) IPCO 2004. LNCS, vol. 3064, pp. 401\u2013415. Springer, Heidelberg (2004). doi: 10.1007\/978-3-540-25960-2_30"},{"issue":"3","key":"26_CR8","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1137\/110839813","volume":"26","author":"V Kaibel","year":"2012","unstructured":"Kaibel, V., Pashkovich, K., Theis, D.O.: Symmetry matters for sizes of extended formulations. SIAM J. Discret. Math. 26(3), 1361\u20131382 (2012)","journal-title":"SIAM J. Discret. Math."},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-540-45198-3_27","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"V Kaibel","year":"2003","unstructured":"Kaibel, V., Remshagen, A.: On the graph-density of random 0\/1-polytopes. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) APPROX\/RANDOM -2003. LNCS, vol. 2764, pp. 318\u2013328. Springer, Heidelberg (2003). doi: 10.1007\/978-3-540-45198-3_27"},{"key":"26_CR10","unstructured":"Makkeh, A., Pourmoradnasseri, M., Theis, D.O.: On the graph of the pedigree polytope. arXiv:1611.08431 (2016)"},{"issue":"6","key":"26_CR11","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1007\/s10958-014-2172-9","volume":"203","author":"A Maksimenko","year":"2014","unstructured":"Maksimenko, A.: The common face of some 0\/1-polytopes with NP-complete non-adjacency relation. J. Math. Sci. 203(6), 823\u2013832 (2014)","journal-title":"J. Math. Sci."},{"issue":"1","key":"26_CR12","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/0095-8956(84)90040-6","volume":"37","author":"D Naddef","year":"1984","unstructured":"Naddef, D.: Pancyclic properties of the graph of some 0\u20131 polyhedra. J. Comb. Theor. Ser. B 37(1), 10\u201326 (1984)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"1","key":"26_CR13","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01581259","volume":"58","author":"DJ Naddef","year":"1993","unstructured":"Naddef, D.J., Pulleyblank, W.R.: The graphical relaxation: a new framework for the symmetric traveling salesman polytope. Math. Program. Ser. A 58(1), 53\u201388 (1993). http:\/\/dx.doi.org\/10.1007\/BF01581259","journal-title":"Math. Program. Ser. A"},{"issue":"1","key":"26_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0095-8956(84)90043-1","volume":"37","author":"DJ Naddef","year":"1984","unstructured":"Naddef, D.J., Pulleyblank, W.R.: Hamiltonicity in (0\u20131)-polyhedra. J. Comb. Theor. Ser. B 37(1), 41\u201352 (1984)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"1","key":"26_CR15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/s10107-006-0060-x","volume":"110","author":"M Oswald","year":"2007","unstructured":"Oswald, M., Reinelt, G., Theis, D.O.: On the graphical relaxation of the symmetric traveling salesman polytope. Math. Program. Ser. B 110(1), 175\u2013193 (2007). http:\/\/dx.doi.org\/10.1007\/s10107-006-0060-x","journal-title":"Math. Program. Ser. B"},{"issue":"1","key":"26_CR16","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/BF01588973","volume":"14","author":"CH Papadimitriou","year":"1978","unstructured":"Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-complete. Math. Program. 14(1), 312\u2013324 (1978)","journal-title":"Math. Program."},{"issue":"2","key":"26_CR17","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.orl.2015.01.004","volume":"43","author":"K Pashkovich","year":"2015","unstructured":"Pashkovich, K., Weltge, S.: Hidden vertices in extensions of polytopes. Oper. Res. Lett. 43(2), 161\u2013164 (2015)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"26_CR18","doi-asserted-by":"crossref","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2012","unstructured":"Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383\u2013412 (2012)","journal-title":"Ann. Math."},{"issue":"3","key":"26_CR19","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/S0895480195283798","volume":"10","author":"A Sarangarajan","year":"1997","unstructured":"Sarangarajan, A.: A lower bound for adjacencies on the traveling salesman polytope. SIAM J. Discret. Math. 10(3), 431\u2013435 (1997)","journal-title":"SIAM J. Discret. Math."},{"key":"26_CR20","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"issue":"1","key":"26_CR21","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0166-218X(93)90169-O","volume":"43","author":"G Sierksma","year":"1993","unstructured":"Sierksma, G.: The skeleton of the symmetric traveling salesman polytope. Discret. Appl. Math. 43(1), 63\u201374 (1993)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"26_CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0166-218X(00)00203-1","volume":"105","author":"G Sierksma","year":"2000","unstructured":"Sierksma, G., Teunter, R.H.: Partial monotonizations of hamiltonian cycle polytopes: dimensions and diameters. Discret. Appl. Math. 105(1), 173\u2013182 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"10","key":"26_CR23","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1016\/j.dam.2010.03.003","volume":"158","author":"DO Theis","year":"2010","unstructured":"Theis, D.O.: A note on the relationship between the graphical traveling salesman polyhedron, the symmetric traveling salesman polytope, and the metric cone. Discret. Appl. Math. 158(10), 1118\u20131120 (2010). http:\/\/dx.doi.org\/10.1016\/j.dam.2010.03.003","journal-title":"Discret. Appl. Math."},{"key":"26_CR24","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.disopt.2013.12.003","volume":"12","author":"DO Theis","year":"2014","unstructured":"Theis, D.O.: On the facial structure of symmetric and graphical traveling salesman polyhedra. Discret. Optim. 12, 10\u201325 (2014). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1572528613000625","journal-title":"Discret. Optim."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53007-9_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T05:35:24Z","timestamp":1498368924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53007-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319530062","9783319530079"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53007-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}