Berthe, Gaétan; Martin, Barnaby; Paulusma, Daniël; Smith, Siani The complexity of \(L(p, q)\)-edge-labelling. (English) Zbl 07767695 Algorithmica 85, No. 11, 3406-3429 (2023). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{G. Berthe} et al., Algorithmica 85, No. 11, 3406--3429 (2023; Zbl 07767695) Full Text: DOI
Borisova, Irina Artëmovna Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space. (Russian. English summary) Zbl 1491.68255 Diskretn. Anal. Issled. Oper. 27, No. 2, 5-16 (2020). MSC: 68U05 68Q17 68T05 PDFBibTeX XMLCite \textit{I. A. Borisova}, Diskretn. Anal. Issled. Oper. 27, No. 2, 5--16 (2020; Zbl 1491.68255) Full Text: DOI MNR
Fu, Bin; Gu, Pengfei; Zhao, Yuming Approximate set union via approximate randomization. (English) Zbl 07336137 Kim, Donghyun (ed.) et al., Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12273, 591-602 (2020). MSC: 68Rxx PDFBibTeX XMLCite \textit{B. Fu} et al., Lect. Notes Comput. Sci. 12273, 591--602 (2020; Zbl 07336137) Full Text: DOI arXiv
Akrida, Eleni C.; Mertzios, George B.; Nikoletseas, Sotiris; Raptopoulos, Christoforos; Spirakis, Paul G.; Zamaraev, Viktor How fast can we reach a target vertex in stochastic temporal graphs? (English) Zbl 1456.68124 J. Comput. Syst. Sci. 114, 65-83 (2020). Reviewer: Charles J. Colbourn (Tempe) MSC: 68R10 68Q25 68Q87 68W25 PDFBibTeX XMLCite \textit{E. C. Akrida} et al., J. Comput. Syst. Sci. 114, 65--83 (2020; Zbl 1456.68124) Full Text: DOI arXiv Link
Ando, Ei; Kijima, Shuji An FPTAS for the volume of some \(\mathcal{V} \)-polytopes – it is hard to compute the volume of the intersection of two cross-polytopes. (English) Zbl 1455.68273 Theor. Comput. Sci. 833, 87-106 (2020). Reviewer: Gabriela Cristescu (Arad) MSC: 68W25 52B11 52B55 68Q17 68U05 68W40 PDFBibTeX XMLCite \textit{E. Ando} and \textit{S. Kijima}, Theor. Comput. Sci. 833, 87--106 (2020; Zbl 1455.68273) Full Text: DOI
Akrida, Eleni C.; Mertzios, George B.; Nikoletseas, Sotiris; Raptopoulos, Christoforos; Spirakis, Paul G.; Zamaraev, Viktor How fast can we reach a target vertex in stochastic temporal graphs? (English) Zbl 1509.68193 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 131, 14 p. (2019). MSC: 68R10 68Q25 68Q87 68W25 PDFBibTeX XMLCite \textit{E. C. Akrida} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 131, 14 p. (2019; Zbl 1509.68193) Full Text: DOI
dos Santos Souza, Uéverton; Protti, Fábio Tractability, hardness, and kernelization lower bound for and/or graph solution. (English) Zbl 1372.05224 Discrete Appl. Math. 232, 125-133 (2017). MSC: 05C99 68R10 68P05 68Q15 PDFBibTeX XMLCite \textit{U. dos Santos Souza} and \textit{F. Protti}, Discrete Appl. Math. 232, 125--133 (2017; Zbl 1372.05224) Full Text: DOI
Yamamoto, Masaki Approximately counting paths and cycles in a graph. (English) Zbl 1358.05140 Discrete Appl. Math. 217, Part 2, 381-387 (2017). MSC: 05C30 05C38 68Q17 PDFBibTeX XMLCite \textit{M. Yamamoto}, Discrete Appl. Math. 217, Part 2, 381--387 (2017; Zbl 1358.05140) Full Text: DOI
Bu, Tian-Ming; Yuan, Chen; Zhang, Peng Computing on binary strings. (English) Zbl 1303.68162 Theor. Comput. Sci. 562, 122-128 (2015). MSC: 68W32 68Q17 PDFBibTeX XMLCite \textit{T.-M. Bu} et al., Theor. Comput. Sci. 562, 122--128 (2015; Zbl 1303.68162) Full Text: DOI arXiv
Cheng, Qi; Hill, Joshua E.; Wan, Daqing Counting value sets: algorithm and complexity. (English) Zbl 1344.11084 Howe, Everett W. (ed.) et al., ANTS X. Proceedings of the tenth algorithmic number theory symposium, San Diego, CA, USA, July 9–13, 2012. Berkeley, CA: Mathematical Sciences Publishers (MSP) (ISBN 978-1-935107-00-2/hbk; 978-1-935107-01-9/ebook). The Open Book Series 1, 235-248 (2013). MSC: 11Y16 11T06 68Q17 PDFBibTeX XMLCite \textit{Q. Cheng} et al., Open Book Ser. 1, 235--248 (2013; Zbl 1344.11084) Full Text: arXiv
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji Holographic reduction, interpolation and hardness. (English) Zbl 1282.68120 Comput. Complexity 21, No. 4, 573-604 (2012). MSC: 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Comput. Complexity 21, No. 4, 573--604 (2012; Zbl 1282.68120) Full Text: DOI
Brantner, Lukas [Manners, Frederick] On the complexity of sails. Appendix by Frederick Manners. (English) Zbl 1282.20044 Pac. J. Math. 258, No. 1, 1-30 (2012). MSC: 20F65 20E06 20F12 20F05 57M07 68Q17 05C90 52B12 PDFBibTeX XMLCite \textit{L. Brantner}, Pac. J. Math. 258, No. 1, 1--30 (2012; Zbl 1282.20044) Full Text: DOI arXiv Link
Yen, William Chung-Kung The connected \(p\)-center problem on block graphs with forbidden vertices. (English) Zbl 1238.68064 Theor. Comput. Sci. 426-427, 13-24 (2012). MSC: 68Q17 05C12 05C85 68R10 PDFBibTeX XMLCite \textit{W. C. K. Yen}, Theor. Comput. Sci. 426--427, 13--24 (2012; Zbl 1238.68064) Full Text: DOI
Kijima, Shuji; Nemoto, Toshio On randomized approximation for finding a level ideal of a poset and the generalized median stable matchings. (English) Zbl 1238.68185 Math. Oper. Res. 37, No. 2, 356-371 (2012). MSC: 68W20 68Q87 68W25 68W40 PDFBibTeX XMLCite \textit{S. Kijima} and \textit{T. Nemoto}, Math. Oper. Res. 37, No. 2, 356--371 (2012; Zbl 1238.68185) Full Text: DOI
Chow, Timothy Y. What is …a natural proof? (English) Zbl 1252.68124 Notices Am. Math. Soc. 58, No. 11, 1586-1587 (2011). Reviewer: Marat M. Arslanov (Kazan) MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{T. Y. Chow}, Notices Am. Math. Soc. 58, No. 11, 1586--1587 (2011; Zbl 1252.68124)
Glaßer, Christian; Pavan, A.; Travers, Stephen The fault tolerance of NP-hard problems. (English) Zbl 1234.68136 Inf. Comput. 209, No. 3, 443-455 (2011). MSC: 68Q17 PDFBibTeX XMLCite \textit{C. Glaßer} et al., Inf. Comput. 209, No. 3, 443--455 (2011; Zbl 1234.68136) Full Text: DOI
Ahn, Hee-Kap; Bae, Sang Won; Demaine, Erik D.; Demaine, Martin L.; Kim, Sang-Sub; Korman, Matias; Reinbacher, Iris; Son, Wanbin Covering points by disjoint boxes with outliers. (English) Zbl 1217.68109 Comput. Geom. 44, No. 3, 178-190 (2011). MSC: 68Q25 52B55 52C22 68Q17 PDFBibTeX XMLCite \textit{H.-K. Ahn} et al., Comput. Geom. 44, No. 3, 178--190 (2011; Zbl 1217.68109) Full Text: DOI
Glaßer, Christian; Selman, Alan L.; Travers, Stephen; Wagner, Klaus W. The complexity of unions of disjoint sets. (English) Zbl 1152.68019 J. Comput. Syst. Sci. 74, No. 7, 1173-1187 (2008). MSC: 68Q17 68Q15 PDFBibTeX XMLCite \textit{C. Glaßer} et al., J. Comput. Syst. Sci. 74, No. 7, 1173--1187 (2008; Zbl 1152.68019) Full Text: DOI
Xia, Mingji Maximum edge-disjoint paths problem in planar graphs. (English) Zbl 1200.05234 Cai, Jin-Yi (ed.) et al., Theory and applications of models of computation. 4th international conference, TAMC 2007, Shanghai, China, May 22–25, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72503-9/pbk). Lecture Notes in Computer Science 4484, 566-572 (2007). MSC: 05C85 05C38 68Q17 68W20 PDFBibTeX XMLCite \textit{M. Xia}, Lect. Notes Comput. Sci. 4484, 566--572 (2007; Zbl 1200.05234) Full Text: DOI
Löbel, Andreas Solving large-scale multiple-depot vehicle scheduling problems. (English) Zbl 0948.90019 Wilson, Nigel H. M. (ed.), Computer-aided transit scheduling. Proceedings, Cambridge, MA, USA, August 1997. Berlin: Springer. Lect. Notes Econ. Math. Syst. 471, 193-220 (1999). MSC: 90B06 90C10 90C06 68M20 90B35 PDFBibTeX XMLCite \textit{A. Löbel}, Lect. Notes Econ. Math. Syst. 471, 193--220 (1999; Zbl 0948.90019)
Blondel, Vincent D.; Tsitsiklis, John N. Complexity of stability and controllability of elementary hybrid systems. (English) Zbl 0943.93044 Automatica 35, No. 3, 479-489 (1999). Reviewer: B.F.Šmarda (Brno) MSC: 93C65 68Q25 93D05 93B05 93C10 93C30 PDFBibTeX XMLCite \textit{V. D. Blondel} and \textit{J. N. Tsitsiklis}, Automatica 35, No. 3, 479--489 (1999; Zbl 0943.93044) Full Text: DOI
Nourani, Yaghout; Andresen, Bjarne Exploration of NP-hard enumeration problems by simulated annealing – the spectrum values of permanents. (English) Zbl 0913.68070 Theor. Comput. Sci. 215, No. 1-2, 51-68 (1999). MSC: 68Q05 PDFBibTeX XMLCite \textit{Y. Nourani} and \textit{B. Andresen}, Theor. Comput. Sci. 215, No. 1--2, 51--68 (1999; Zbl 0913.68070) Full Text: DOI
Toker, Onur; Özbay, Hitay On the complexity of purely complex \(\mu\) computation and related problems in multidimensional systems. (English) Zbl 0905.93018 IEEE Trans. Autom. Control 43, No. 3, 409-414 (1998). Reviewer: M.M.Konstantinov (Sofia) MSC: 93B40 93B35 93B50 93B36 68Q15 68Q25 PDFBibTeX XMLCite \textit{O. Toker} and \textit{H. Özbay}, IEEE Trans. Autom. Control 43, No. 3, 409--414 (1998; Zbl 0905.93018) Full Text: DOI
Fu, Bin; Li, Hong-Zhou Closeness of NP-hard sets to other complexity classes. (English) Zbl 0807.68031 SIAM J. Comput. 23, No. 2, 255-260 (1994). Reviewer: U.Schöning (Ulm) MSC: 68Q15 68Q25 03D15 PDFBibTeX XMLCite \textit{B. Fu} and \textit{H.-Z. Li}, SIAM J. Comput. 23, No. 2, 255--260 (1994; Zbl 0807.68031) Full Text: DOI
Welsh, D. J. A. The computational complexity of knot and matroid polynomials. (English) Zbl 0816.57008 Discrete Math. 124, No. 1-3, 251-269 (1994). MSC: 57M25 57M15 68Q25 68R10 05C99 05B35 PDFBibTeX XMLCite \textit{D. J. A. Welsh}, Discrete Math. 124, No. 1--3, 251--269 (1994; Zbl 0816.57008) Full Text: DOI
Fu, Bin; Li, Hong-zhou On symmetric differences of NP-hard sets with weakly P-selective sets. (English) Zbl 0805.68042 Theor. Comput. Sci. 120, No. 2, 279-291 (1993). Reviewer: U.Schöning (Ulm) MSC: 68Q15 03D15 PDFBibTeX XMLCite \textit{B. Fu} and \textit{H.-z. Li}, Theor. Comput. Sci. 120, No. 2, 279--291 (1993; Zbl 0805.68042) Full Text: DOI
Formann, Michael Algorithms for geometric packing and scaling problems. (English) Zbl 0836.68116 Berlin: FB Math., FU Berlin, 115 p. (1992). Reviewer: H.-D.Hecker (Jena) MSC: 68U05 68W10 PDFBibTeX XMLCite \textit{M. Formann}, Algorithms for geometric packing and scaling problems. Berlin: FB Math., FU Berlin (1992; Zbl 0836.68116)
Barthélemy, J.-P.; Cohen, G.; Lobstein, A. Algorithmic complexity and communication problems. (Complexité algorithmique et problèmes de communications. Préface de M. Minoux.) (French) Zbl 0765.68005 Collection Technique et Scientifique des Télécommunications. Paris etc.: Masson. XXVII, 228 p. (1992). Reviewer: C.Calude (Auckland) MSC: 68-02 68Q25 94-02 PDFBibTeX XMLCite \textit{J. P. Barthélemy} et al., Complexité algorithmique et problèmes de communications. Préface de M. Minoux. Paris etc.: Masson (1992; Zbl 0765.68005)
Papadimitriou, Christos H.; Yannakakis, Mihalis Shortest paths without a map. (English) Zbl 0733.68065 Theor. Comput. Sci. 84, No. 1, 127-150 (1991). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{C. H. Papadimitriou} and \textit{M. Yannakakis}, Theor. Comput. Sci. 84, No. 1, 127--150 (1991; Zbl 0733.68065) Full Text: DOI
Hobby, David Finding type sets is NP-hard. (English) Zbl 0757.08005 Int. J. Algebra Comput. 1, No. 4, 437-444 (1991). MSC: 08B99 68Q25 PDFBibTeX XMLCite \textit{D. Hobby}, Int. J. Algebra Comput. 1, No. 4, 437--444 (1991; Zbl 0757.08005) Full Text: DOI
Jaeger, François; Vertigan, D. L.; Welsh, D. J. A. On the computational complexity of the Jones and Tutte polynomials. (English) Zbl 0747.57006 Math. Proc. Camb. Philos. Soc. 108, No. 1, 35-53 (1990). Reviewer: B.Zimmermann (Trieste) MSC: 57M25 57M15 68Q25 68R10 PDFBibTeX XMLCite \textit{F. Jaeger} et al., Math. Proc. Camb. Philos. Soc. 108, No. 1, 35--53 (1990; Zbl 0747.57006) Full Text: DOI
Savage, John E.; Wloka, Markus G. On parallelizing graph-partitioning heuristics. (English) Zbl 0765.68162 Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 476-489 (1990). MSC: 68R10 68W15 68Q25 PDFBibTeX XMLCite \textit{J. E. Savage} and \textit{M. G. Wloka}, Lect. Notes Comput. Sci. 443, 476--489 (1990; Zbl 0765.68162)
Aupperle, Larry; Keil, Mark J. Polynomial algorithms for restricted Euclidean p-centre problems. (English) Zbl 0666.68036 Discrete Appl. Math. 23, No. 1, 25-31 (1989). MSC: 68Q25 52A37 PDFBibTeX XMLCite \textit{L. Aupperle} and \textit{M. J. Keil}, Discrete Appl. Math. 23, No. 1, 25--31 (1989; Zbl 0666.68036) Full Text: DOI
Wang, D. W.; Kuo, Yuesun A study on two geometric location problems. (English) Zbl 0675.68071 Inf. Process. Lett. 28, No. 6, 281-286 (1988). Reviewer: R.Klette MSC: 68U99 68Q25 52A37 68R99 PDFBibTeX XMLCite \textit{D. W. Wang} and \textit{Y. Kuo}, Inf. Process. Lett. 28, No. 6, 281--286 (1988; Zbl 0675.68071) Full Text: DOI
Dyer, M. E.; Frieze, A. M. On the complexity of computing the volume of a polyhedron. (English) Zbl 0668.68049 SIAM J. Comput. 17, No. 5, 967-974 (1988). Reviewer: N.Kornunko MSC: 68Q25 52Bxx PDFBibTeX XMLCite \textit{M. E. Dyer} and \textit{A. M. Frieze}, SIAM J. Comput. 17, No. 5, 967--974 (1988; Zbl 0668.68049) Full Text: DOI Backlinks: MO
Platzman, Loren K.; Ammons, Jane C.; Bartholdi, John J. III A simple and efficient algorithm to compute tail probabilities from transforms. (English) Zbl 0655.65150 Oper. Res. 36, No. 1, 137-144 (1988). Reviewer: K.Uosaki MSC: 65C99 68W99 PDFBibTeX XMLCite \textit{L. K. Platzman} et al., Oper. Res. 36, No. 1, 137--144 (1988; Zbl 0655.65150) Full Text: DOI
Sherali, Hanif D.; Nordai, Frederick L. NP-hard, capacitated, balanced p-median problems on a chain graph with a continuum of link demands. (English) Zbl 0651.90025 Math. Oper. Res. 13, No. 1, 32-49 (1988). Reviewer: W.Deuber MSC: 90B05 90C90 68Q25 PDFBibTeX XMLCite \textit{H. D. Sherali} and \textit{F. L. Nordai}, Math. Oper. Res. 13, No. 1, 32--49 (1988; Zbl 0651.90025) Full Text: DOI
Wakabayashi, Yoshiko Aggregation of binary relations: algorithmic and polyhedral investigations. (English) Zbl 0606.68036 Naturwissenschaftliche Fakultät der Universität Augsburg. 191 p. (1986). MSC: 68Q25 03E20 90C05 PDFBibTeX XML
Megiddo, Nimrod; Supowit, Kenneth J. On the complexity of some common geometric location problems. (English) Zbl 0534.68032 SIAM J. Comput. 13, 182-196 (1984). Reviewer: D.Yu.Grigorev MSC: 68Q25 PDFBibTeX XMLCite \textit{N. Megiddo} and \textit{K. J. Supowit}, SIAM J. Comput. 13, 182--196 (1984; Zbl 0534.68032) Full Text: DOI
Lolli, Gabriele Complessita delle teorie. (Italian) Zbl 0525.03030 Atti degli incontri di logica matematica, Siena/Italia 1982, 159-182 (1983). MSC: 03D15 03F20 03B25 68Q25 PDFBibTeX XML
Kariv, O.; Hakimi, S. L. An algorithmic approach to network location problems. II: The p-medians. (English) Zbl 0432.90075 SIAM J. Appl. Math. 37, 539-560 (1979). MSC: 90C35 05C05 68Q25 94C15 90B22 05C35 68R10 PDFBibTeX XMLCite \textit{O. Kariv} and \textit{S. L. Hakimi}, SIAM J. Appl. Math. 37, 539--560 (1979; Zbl 0432.90075) Full Text: DOI