Mavronicolas, Marios; Monien, Burkhard; Wagner, Klaus W. Weighted Boolean formula games. (English) Zbl 1331.68112 Zaroliagis, Christos (ed.) et al., Algorithms, probability, networks, and games. Scientific papers and essays dedicated to Paul G. Spirakis on the occasion of his 60th birthday. Cham: Springer (ISBN 978-3-319-24023-7/pbk; 978-3-319-24024-4/ebook). Lecture Notes in Computer Science 9295, 49-86 (2015). MSC: 68Q25 91A10 91A80 PDFBibTeX XMLCite \textit{M. Mavronicolas} et al., Lect. Notes Comput. Sci. 9295, 49--86 (2015; Zbl 1331.68112) Full Text: DOI
Mavronicolas, Marios; Monien, Burkhard The complexity of pure equilibria in mix-weighted congestion games on parallel links. (English) Zbl 1338.68114 Inf. Process. Lett. 115, No. 12, 927-931 (2015). MSC: 68Q25 68Q17 91A10 91A43 PDFBibTeX XMLCite \textit{M. Mavronicolas} and \textit{B. Monien}, Inf. Process. Lett. 115, No. 12, 927--931 (2015; Zbl 1338.68114) Full Text: DOI
Dumrauf, Dominic; Monien, Burkhard On the \(\mathcal {PLS}\)-complexity of maximum constraint assignment. (English) Zbl 1259.68090 Theor. Comput. Sci. 469, 24-52 (2013). MSC: 68Q25 90C27 PDFBibTeX XMLCite \textit{D. Dumrauf} and \textit{B. Monien}, Theor. Comput. Sci. 469, 24--52 (2013; Zbl 1259.68090) Full Text: DOI
Dumrauf, Dominic; Monien, Burkhard Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete. (English) Zbl 1284.91068 Parallel Process. Lett. 22, No. 4, Article ID 1250014, 11 p. (2012). MSC: 91A40 68Q25 91A05 91A43 68M14 PDFBibTeX XMLCite \textit{D. Dumrauf} and \textit{B. Monien}, Parallel Process. Lett. 22, No. 4, Article ID 1250014, 11 p. (2012; Zbl 1284.91068) Full Text: DOI
Gairing, Martin; Lücking, Thomas; Monien, Burkhard; Tiemann, Karsten Nash equilibria, the price of anarchy and the fully mixed Nash equilibrium conjecture. (English) Zbl 1084.91006 Caires, Luís (ed.) et al., Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11–15, 2005. Proceedings. Berlin: Springer (ISBN 3-540-27580-0/pbk). Lecture Notes in Computer Science 3580, 51-65 (2005). MSC: 91A10 91B52 68Q25 91-02 PDFBibTeX XMLCite \textit{M. Gairing} et al., Lect. Notes Comput. Sci. 3580, 51--65 (2005; Zbl 1084.91006) Full Text: DOI
Gairing, Martin; Lücking, Thomas; Mavronicolas, Marios; Monien, Burkhard; Spirakis, Paul Extreme Nash equilibria. (English) Zbl 1257.68081 Blundo, Carlo (ed.) et al., Theoretical computer science. 8th Italian conference, ICTCS 2003, Bertinoro, Italy, October 13–15, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20216-1/pbk). Lect. Notes Comput. Sci. 2841, 1-20 (2003). MSC: 68Q25 68Q17 68W25 91A06 PDFBibTeX XMLCite \textit{M. Gairing} et al., Lect. Notes Comput. Sci. 2841, 1--20 (2003; Zbl 1257.68081) Full Text: DOI
Feldmann, Rainer; Sensen, Norbert; Monien, Burkhard; Schlake, Oliver Algorithms for the consistency analysis in scenario projects. (English) Zbl 1101.68040 Pardalos, Panos M. (ed.) et al., Combinatorial and global optimization. Singapore: World Scientific (ISBN 981-02-4802-4). Ser. Appl. Math., Singap. 14, 55-73 (2002). Reviewer: Stefan Nickel (Saarbrücken) MSC: 68Q25 90C27 90C60 PDFBibTeX XMLCite \textit{R. Feldmann} et al., Ser. Appl. Math., Singap. 14, 55--73 (2002; Zbl 1101.68040)
Feldmann, R.; Hromkovič, Juraj; Madhavapeddy, S.; Monien, B.; Mysliwietz, P. Optimal algorithms for dissemination of information in generalized communication modes. (English) Zbl 0823.68041 Discrete Appl. Math. 53, No. 1-3, 55-78 (1994). MSC: 68Q25 05C90 68R10 94C15 PDFBibTeX XMLCite \textit{R. Feldmann} et al., Discrete Appl. Math. 53, No. 1--3, 55--78 (1994; Zbl 0823.68041) Full Text: DOI
Hromkovič, Juraj; Jeschke, Claus-Dieter; Monien, Burkhard Optimal algorithms for dissemination of information in some interconnection networks. (English) Zbl 0773.68007 Algorithmica 10, No. 1, 24-40 (1993). MSC: 68M10 68Q25 PDFBibTeX XMLCite \textit{J. Hromkovič} et al., Algorithmica 10, No. 1, 24--40 (1993; Zbl 0773.68007) Full Text: DOI
Haralambides, J.; Makedon, F.; Monien, B. Bandwidth minimization: An approximation algorithm for caterpillars. (English) Zbl 0767.68081 Math. Syst. Theory 24, No. 3, 169-177 (1991). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{J. Haralambides} et al., Math. Syst. Theory 24, No. 3, 169--177 (1991; Zbl 0767.68081) Full Text: DOI
Hromkovič, Juraj; Monien, Burkhard The bisection problem for graphs of degree 4. (Configuring transputer systems). (English) Zbl 0768.68145 Mathematical foundations of computer science, Proc. 16th Int. Symp., Kazimierz Dolny/Pol. 1991, Lect. Notes Comput. Sci. 520, 211-220 (1991). MSC: 68R10 68Q25 05C85 PDFBibTeX XMLCite \textit{J. Hromkovič} and \textit{B. Monien}, Lect. Notes Comput. Sci. 520, 211--220 (1991; Zbl 0768.68145)
Hromkovič, Juraj; Jeschke, Claus-Dieter; Monien, Burkhard Optimal algorithms for dissemination of information in some interconnection networks. (English) Zbl 0733.68007 Mathematical foundations of computer science, Proc. 15th Symp., MFCS ’90, Banská Bystrica/Czech. 1990, Lect. Notes Comput. Sci. 452, 337-346 (1990). MSC: 68M10 68M07 68Q25 PDFBibTeX XML
Menzel, K.; Monien, B. Weighted parallel triangulation of simple polygons. (English) Zbl 0771.68105 Graph-theoretic concepts in computer science, Proc. 15th Int. Workshop, WG ’89, Castle Rolduc/Neth. 1989, Lect. Notes Comput. Sci. 411, 302-315 (1990). MSC: 68U05 68Q25 PDFBibTeX XMLCite \textit{K. Menzel} and \textit{B. Monien}, Lect. Notes Comput. Sci. 411, 302--315 (1990; Zbl 0771.68105)
Monien, B.; Sudborough, I. H. Min Cut is NP-complete for edge weighted trees. (English) Zbl 0657.68034 Theor. Comput. Sci. 58, No. 1-3, 209-229 (1988). Reviewer: A.Brandstädt MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{B. Monien} and \textit{I. H. Sudborough}, Theor. Comput. Sci. 58, No. 1--3, 209--229 (1988; Zbl 0657.68034) Full Text: DOI
Monien, Burkhard; Sudborough, I. Hal Simulating binary trees on hypercubes. (English) Zbl 0652.68086 VLSI algorithms and architectures, Proc. 3rd Aegean Workshop Comput., Corfu/Greece 1988, Lect. Notes Comput. Sci. 319, 170-180 (1988). MSC: 68R10 68Q05 05C10 68N99 68Q25 PDFBibTeX XML
Leung, Joseph Y.-T.; Monien, Burkhard On the complexity of deadlock recovery. (English) Zbl 0642.68068 Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 9, 323-342 (1986). MSC: 68Q25 68N25 PDFBibTeX XMLCite \textit{J. Y. T. Leung} and \textit{B. Monien}, Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 9, 323--342 (1986; Zbl 0642.68068)
Monien, Burkhard The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. (English) Zbl 0624.68059 SIAM J. Algebraic Discrete Methods 7, 505-512 (1986). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{B. Monien}, SIAM J. Algebraic Discrete Methods 7, 505--512 (1986; Zbl 0624.68059) Full Text: DOI Link
Monien, B.; Sudborough, I. H. Min cut is NP-complete for edge weighted trees. (English) Zbl 0594.68042 Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 265-274 (1986). MSC: 68Q25 05C10 05C05 PDFBibTeX XML
Monien, Burkhard; Sudborough, Ivan Hal Bandwidth contrained NP-complete problems. (English) Zbl 0618.68043 Theor. Comput. Sci. 41, 141-167 (1985). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{B. Monien} and \textit{I. H. Sudborough}, Theor. Comput. Sci. 41, 141--167 (1985; Zbl 0618.68043) Full Text: DOI
Leung, Joseph Y.-T.; Monien, Burkhard On the complexity of deadlock recovery. (English) Zbl 0604.68045 Theoretical aspects of computer science, 2nd ann. Symp., Saarbrücken/Ger. 1985, Lect. Notes Comput. Sci. 182, 208-218 (1985). MSC: 68Q25 68N25 PDFBibTeX XML
Monien, B.; Speckenmeyer, E. Solving satisfiability in less than \(2^ n\) steps. (English) Zbl 0603.68092 Discrete Appl. Math. 10, 287-295 (1985). MSC: 68T15 68Q25 PDFBibTeX XMLCite \textit{B. Monien} and \textit{E. Speckenmeyer}, Discrete Appl. Math. 10, 287--295 (1985; Zbl 0603.68092) Full Text: DOI
Monien, B. How to find long paths efficiently. (English) Zbl 0603.68069 Analysis and design of algorithms for combinatorial problems, Ann. Discrete Math. 25, 239-254 (1985). MSC: 68R10 68Q25 05C38 PDFBibTeX XML
Monien, B. The complexity of embedding graphs into binary trees. (English) Zbl 0588.68019 Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 300-309 (1985). Reviewer: G.Slutzki MSC: 68Q25 05C10 05C05 68R10 PDFBibTeX XML
Monien, Burkhard; Speckenmeyer, Ewald Ramsey numbers and an approximation algorithm for the vertex cover problem. (English) Zbl 0596.05048 Frege conference, Proc. Int. Conf., Schwerin/Ger. 1984, Math. Res. 20, 345-353 (1984). Reviewer: M.M.Sysło MSC: 05C55 05C70 68Q25 PDFBibTeX XML
Monien, B. Deterministic two-way one-head pushdown automata are very powerful. (English) Zbl 0549.68041 Inf. Process. Lett. 18, 239-242 (1984). MSC: 68Q05 68Q25 68Q45 PDFBibTeX XMLCite \textit{B. Monien}, Inf. Process. Lett. 18, 239--242 (1984; Zbl 0549.68041) Full Text: DOI Link
Monien, B. The complexity of determining paths of length k. (English) Zbl 0549.68066 Graphtheoretic concepts in computer science, Proc. int. Workshop, Osnabrück 1983, 241-251 (1983). MSC: 68R10 68Q25 05C38 PDFBibTeX XML
Monien, B. The complexity of determining a shortest cycle of even length. (English) Zbl 0516.68041 Computing 31, 355-369 (1983). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{B. Monien}, Computing 31, 355--369 (1983; Zbl 0516.68041) Full Text: DOI
Monien, B. The complexity of determining a shortest cycle of even length. (English) Zbl 0549.68065 Graphtheoretic concepts in computer science, Proc. 8th Conf., Neunkirchen/Ger. 1982, 195-208 (1982). MSC: 68R10 68Q25 05C38 PDFBibTeX XML
Monien, B.; Schulz, Reinald Four approximation algorithms for the feedback vertex set problem. (English) Zbl 0549.68064 Graphtheoretic concepts in computer science, Proc. 7th Conf., Linz/Austria 1981, 315-326 (1982). MSC: 68R10 68Q25 PDFBibTeX XML
Monien, Burkhard; Sudborough, Ivan Hal On eliminating nondeterminism from Turing machines which use less than logarithm worktape space. (English) Zbl 0493.68046 Theor. Comput. Sci. 21, 237-253 (1982). MSC: 68Q05 68Q25 68R10 PDFBibTeX XMLCite \textit{B. Monien} and \textit{I. H. Sudborough}, Theor. Comput. Sci. 21, 237--253 (1982; Zbl 0493.68046) Full Text: DOI
Monien, Burkhard; Speckenmeyer, Ewald; Vornberger, Oliver Upper bounds for covering problems. (English) Zbl 0508.90065 Methods Oper. Res. 43, 419-431 (1981). MSC: 90C10 68Q25 PDFBibTeX XMLCite \textit{B. Monien} et al., Methods Oper. Res. 43, 419--431 (1981; Zbl 0508.90065)
Monien, Burkhard On the LBA problem. (English) Zbl 0474.68064 Fundamentals of computation theory, Proc. int. FCT-Conf., Szeged/ Hung. 1981, Lect. Notes Comput. Sci. 117, 265-280 (1981). MSC: 68Q05 68Q25 68-02 PDFBibTeX XML
Monien, Burkhard; Sudborough, Ivan Hal Bounding the bandwidth of NP-complete problems. (English) Zbl 0454.68072 Graphtheoretic concepts in computer science, Proc. int. Workshop, Bad Honnef 1980, Lect. Notes Comput. Sci. 100, 279-292 (1981). MSC: 68R10 68Q25 PDFBibTeX XML
Monien, B.; Urmetzer, N.; Vornberger, O. A consideration of the travelling-salesman problem using the assignment problem. (English) Zbl 0471.90091 Discrete structures and algorithms, Proc. Workshop, 5th Conf. graphtheor. Concepts Comput. Sci., Berlin 1979, 167-179 (1980). MSC: 90C35 05C35 68Q25 05C38 05C05 05C20 PDFBibTeX XML
Monien, Burkhard On a subclass of pseudopolynomial problems. (English) Zbl 0453.68016 Mathematical foundations of computer science, Proc. 9th Symp., Rydzyna/Pol. 1980, Lect. Notes Comput. Sci. 88, 414 (1980). MSC: 68Q25 PDFBibTeX XML
Monien, Burkhard About the derivation languages of grammars and machines. (English) Zbl 0365.68079 Automata, languages and programming, 4th Colloq., Turku 1977, Lect. Notes Comput. Sci. 52, 337-351 (1977). MSC: 68Q45 68Q25 PDFBibTeX XML
Monien, B. The LBA-problem and the transformability of the class \(\delta^2\). (English) Zbl 0365.68046 Theor. Comput. Sci., 3rd GI Conf., Darmstadt 1977, Lect. Notes Comput. Sci. 48, 339-350 (1977). MSC: 68Q25 68Q45 03D10 PDFBibTeX XML
Monien, Burkhard Transformational methods and their application to complexity problems. Corrigenda. (English) Zbl 0365.02026 Acta Inf. 8, 383-384 (1977). MSC: 03D10 03D05 68Q25 PDFBibTeX XMLCite \textit{B. Monien}, Acta Inf. 8, 383--384 (1977; Zbl 0365.02026) Full Text: DOI
Monien, Burkhard The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet. (English) Zbl 0357.68073 Acta Inf. 8, 371-382 (1977). MSC: 68Q45 68Q25 PDFBibTeX XMLCite \textit{B. Monien}, Acta Inf. 8, 371--382 (1977; Zbl 0357.68073) Full Text: DOI
Monien, Burkhard A recursive and a grammatical characterization of the exponential-time languages. (English) Zbl 0355.68056 Theor. Comput. Sci. 3, 61-74 (1977). MSC: 68Q45 68Q25 03D20 PDFBibTeX XMLCite \textit{B. Monien}, Theor. Comput. Sci. 3, 61--74 (1977; Zbl 0355.68056) Full Text: DOI Link
Monien, Burkhard Über die Komplexität der Ableitungssprachen von Grammatiken und Maschinen. (German) Zbl 0373.68045 Bericht. No. 35. Dortmund: Abteilung Informatik der Universität Dortmund. 36 S. (1976). Reviewer: P. Turakainen MSC: 68Q45 68Q25 PDFBibTeX XML
Monien, Burkhard Transformational methods and their application to complexity problems. (English) Zbl 0329.02015 Acta Inf. 6, 95-108 (1976). MSC: 03D10 68Q25 03D05 68Q45 PDFBibTeX XMLCite \textit{B. Monien}, Acta Inf. 6, 95--108 (1976; Zbl 0329.02015) Full Text: DOI
Monien, Burkhard Relationships between pushdown automata with counters and complexity classes. (English) Zbl 0348.68032 Math. Syst. Theory 9, 248-264 (1975). MSC: 68Q25 68Q45 PDFBibTeX XMLCite \textit{B. Monien}, Math. Syst. Theory 9, 248--264 (1975; Zbl 0348.68032) Full Text: DOI
Monien, Burkhard About the deterministic simulation of nondeterministic (log n)-tape bounded Turing machines. (English) Zbl 0341.68032 Autom. Theor. form. Lang., 2nd GI Conf., Kaiserslautern 1975, Lect. Notes Comput. Sci. 33, 118-126 (1975). MSC: 68Q25 68Q45 03D10 PDFBibTeX XML
Monien, Burkhard Characterizations of time-bounded computations by limited primitive recursion. (English) Zbl 0289.68015 Automata, Languages, Progr.; 2nd Colloqu., Univ. Saarbrücken, Lecture Notes Computer Sci. 14, 280-293 (1974). MSC: 68Q25 68Q45 PDFBibTeX XML
Monien, Burkhard Beschreibung von Zeitkomplexitätsklassen bei Turingmaschinen durch andere Automatenmodelle. (German) Zbl 0286.68026 Elektron. Inform.-verarb. Kybernetik 10, 37-51 (1974). MSC: 68Q25 03D10 68Q45 PDFBibTeX XMLCite \textit{B. Monien}, Elektron. Informationsverarbeitung Kybernetik 10, 37--51 (1974; Zbl 0286.68026)
Monien, B. On the simulation of time bounded machines. (English) Zbl 0283.68027 GI, Ges. Informatik, 1. Fachtagung Automatentheorie Formale Sprachen, Bonn 1973, Lecture Notes Comput. Sci. 2, 239-248 (1973). MSC: 68Q25 68U20 PDFBibTeX XML
Monien, Burkhard Relationships between pushdown automata and tape-bounded Turing machines. (English) Zbl 0268.68032 Automata, Languages, Programming, Proc. Sympos. Inst. Rech. Informatique Automatique (IRIA), Rocquencourt 1972, 575-583 (1973). MSC: 68Q25 68Q45 03D10 68N01 PDFBibTeX XML