Papers in Reviewed Journals

  1. K. Makino and T. Ibaraki, The maximum latency of partially defined positive Boolean functions, The Transactions of the IEICE, J76-D-1 (1993) 409-416 (in Japanese).
  2. K. Makino and T. Ibaraki, Interior and exterior functions of Boolean functions, Discrete Applied Mathematics, 69 (1996) 209-231.
  3. K. Makino, K. Yano and T. Ibaraki, Positive and Horn decomposability of partially defined Boolean functions, Discrete Applied Mathematics, 74 (1997) 251-274.
  4. K. Makino and T. Ibaraki, The maximum latency and identification of positive Boolean functions, SIAM Journal on Computing, 26 (1997) 1363-1383.
  5. K. Makino and T. Ibaraki, Inner-core and outer-core functions of partially defined Boolean functions, Discrete Applied Mathematics, 96-97 (1999) 443-460.
  6. J. C. Bioch, T. Ibaraki and K. Makino, Minimum self-dual decompositions of positive dual-minor Boolean functions, Discrete Applied Mathematics, 96-97 (1999) 307-326.
  7. E. Boros, T. Ibaraki and K. Makino, Error-free and best-fit extensions of partially defined Boolean functions, Information and Computation, 140 (1998) 254-283.
  8. K. Makino and T. Ibaraki, A fast and simple algorithm for identifying 2-monotonic positive Boolean functions, Journal of Algorithms, 26 (1998) 291-305.
  9. H. Nagamochi, K. Makino, D.-Z. Zeng, M. Murata and T. Ibaraki, Convexity of elementary flow game, The Transactions of the IEICE, J81-D-I (1998) 666-676 (in Japanese).
  10. T. Eiter, T. Ibaraki and K. Makino, Double Horn functions, Information and Computation, 144 (1998) 155-190.
  11. K. Makino, K. Hatanaka and T. Ibaraki, Horn extensions of a partially defined Boolean function, SIAM Journal on Computing, 28 (1999) 2168-2186.
  12. E. Boros, T. Ibaraki and K. Makino, Logical analysis of binary data with missing bits, Artificial Intelligence, 107 (1999) 219-263.
  13. T. Ibaraki, A. Kogan and K. Makino, Functional dependencies in Horn theories, Artificial Intelligence, 108 (1999) 1-30.
  14. T. Eiter, T. Ibaraki and K. Makino, Bidual Horn functions and extensions, Discrete Applied Mathematics, 96 (1999) 55-88.
  15. K. Makino, T. Suda, T. Ono, and T. Ibaraki, Data analysis by positive decision trees, IEICE Transactions on Information and Systems, E82-D (1999) 76-88.
  16. T. Eiter, T. Ibaraki and K. Makino, Computing intersections of Horn theories for reasoning with models, Artificial Intelligence, 110 (1999) 57-101.
  17. T. Eiter, T. Ibaraki and K. Makino, On the difference of Horn theories, Journal of Computer and System Sciences, 61 (2000) 478-507.
  18. E. Boros, V. Gurvich, L. Khachiyan and K. Makino, Dual-bounded generating problems: partial and multiple transversals of a Hypergraph, SIAM Journal on Computing, 30 (2001) 2036 - 2050.
  19. K. Makino, Y. Uno and T. Ibaraki, On minimum edge ranking spanning trees, Journal of Algorithms, 38 (2001) 411-437.
  20. T. Eiter, T. Ibaraki and K. Makino, Disjunction of Horn theories and their cores, SIAM Journal on Computing, 31 (2001) 269 - 288.
  21. T. Ibaraki, A. Kogan and K. Makino, On functional dependencies in q-Horn theories, Artificial Intelligence, 131 (2001) 171-187.
  22. K. Makino and T. Kameda, Transformation of regular non-dominated coteries, SIAM Journal on Discrete Mathematics, 14 (2001) 381-407.
  23. T. Eiter, T. Ibaraki and K. Makino, Decision lists and related Boolean functions, Theoretical Computer Science, 270 (2002) 493-524.
  24. K. Makino, A linear time algorithm for recognizing regular Boolean functions, Journal of Algorithms, 43 (2002) 155-176.
  25. K. Arata, S. Iwata, K. Makino and S. Fujishige, Locating sources to meet flow demands in undirected networks, Journal of Algorithms, 42 (2002) 54-68.
  26. T. Eiter, T. Ibaraki and K. Makino, Recognition and dualization of disguised didual Horn functions, Information Processing Letters, 82 (2002) 283-291.
  27. H. Ono, K. Makino and T. Ibaraki, Logical analysis of data with decomposable structures, Theoretical Computer Science, 289 (2002) 977-995.
  28. S. Mamada, K. Makino, S. Fujishige: Optimal sink location problem for dynamic flows in a tree network, IEICE Transactions on Fundamentals, E85-A (2002) 1020-1025.
  29. K. Makino, M. Yamashita and T. Kameda, Max- and min-neighborhood monopolies, Algorithmica, 34 (2002) 240-260.
  30. K. Makino, T. Takabatake, and S. Fujishige, A simple matching algorithm for regular bipartite graphs, Information Processing Letters 84, (2002) 189-193.
  31. E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan and K. Makino, Dual-bounded generating problems: all minimal integer solutions for a monotone system of linear inequalities, SIAM Journal on Computing 31 (2002) 1624-1643.
  32. K. Makino: Efficient Dualization of O(log n)-term monotone disjunctive normal forms, Discrete Applied Mathematics, 126 (2003) 305-312.
  33. E. Boros, T. Ibaraki and K. Makino, Variations on extending partially defined Boolean functions with missing bits, Information and Computation, 180 (2003) 53-70.
  34. T. Ibaraki, A. Kogan and K. Makino, Inferring Minimal Functional Dependencies in Horn and q-Horn theories, Annals of Mathematics and Artificial Intelligence 38 (2003) 233-255.
  35. T. Eiter, G. Gottlob, K. Makino, New Results on Monotone Dualization and Generating Hypergraph Transversals, SIAM Journal on Computing 32 (2003) 514-537.
  36. K. Makino, T. Ono and T. Ibaraki, Interior and exterior functions of positive Boolean functions, Discrete Applied Mathematics, 130 (2003) 417-436.
  37. E. Boros, T. Horiyama, T. Ibaraki, K. Makino and M. Yagiura, Finding small sets of essential attributes in binary data, Annals of Mathematics and Artificial Intelligence, 39 (2003) 223-257.
  38. E. Boros, V. Gurvich, L. Khachiyan and K. Makino, On maximal frequent and minimal infrequent sets in binary matrices, Annals of Mathematics and Artificial Intelligence, 39 (2003) 211-221.
  39. H. Ito, K. Makino, K. Arata, S. Honami, Y. Itatsu, and S. Fujishige, Source Location Problem with Flow Requirements in Directed Networks, Optimization Methods and Software, 18 (2003) 427-435.
  40. S. Fujishige, K. Makino, T. Takabatake, and Kenji Kashiwabara Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2, Discrete Mathematics, 280 (2004) 13-27.
  41. E. Boros, V. Gurvich, L. Khachiyan and K. Makino, Dual-bounded generating problems: Weighted transversals of a hypergraph, Discrete Applied Mathematics, 142 (2004) 1-15.
  42. S. Mamada, T. Uno, K. Makino and S. Fujishige, A tree partitioning problem arising from an evacuation problem in tree dynamic networks, Journal of the Operations Research Society of Japan, 48 (2005) 196-206.
  43. L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, On the Complexity of Some Enumeration Problems for Matroids, SIAM Journal on Discrete Mathematics 19 (2005) 966-984.
  44. Y. Asahiro, T. Horiyama, K. Makino, H. Ono, T. Sakuma, M. Yamashita, How to collect balls moving in the Euclidean plane, Discrete Applied Mathematics 154 (2006) 2247-2262.
  45. K. Makino, Y. Uno, T. Ibaraki, Minimum edge ranking spanning trees of split graphs, Discrete Applied Mathematics 154 (2006) 2373-2386.
  46. S. Mamada, T. Uno, K. Makino, S. Fujishige, An O(n log^2 n) algorithm for the optimal sink location problem in dynamic tree networks, Discrete Applied Mathematics 154 (2006) 2387-2401.
  47. L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, Enumerating disjunctions and conjunctions of paths and cuts in reliability theory, Discrete Applied Mathematics 155 (2007) 137-149.
  48. L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data, Theoretical Computer Science 379 (2007) 361-376.
  49. T. Eiter, K. Makino, Computing all abductive explanations from Horn theories, Journal of the ACM 54 (2007) 24:1-24:54.
  50. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, K. Makino, Enumerating spanning and connected subsets in graphs and matroids, Journal of the Operations Research Society of Japan 50 (2007), 325-338.
  51. T. Eiter, K. Makino, G. Gottlob, Computational aspects of monotone dualization: A brief survey, Discrete Applied Mathematics 156 (2008) 2035-2049.
  52. M. Sakashita, K. Makino, S. Fujishige, Minimizing a monotone concave function with laminar covering constraints Discrete Applied Mathematics 156 (2008) 2004-2019.
  53. M. Sakashita, K. Makino, S. Fujishige, Minimum cost source location problems with flow requirements, Algorithmica 50 (2008) 555-583.
  54. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, K. Makino, Generating cut conjunctions in graphs and related problems, Algorithmica 51 (2008) 239-263.
  55. D. Gaur and K. Makino, On the fractional chromatic number of monotone self-dual Boolean functions, Discrete Mathematics 309 (2009) 867-877.
  56. E. Boros, V. Gurvich, K. Makino, Minimal and locally minimal games and game forms, Discrete Mathematics 309 (2009) 4456-4468.
  57. M. Sakashita, K. Makino, H. Nagamochi, S. Fujishige, Minimum transversals in posimodular systems, SIAM Journal on Discrete Mathematics 23 (2009) 858-871.
  58. K. Makino, S. Tamaki, M. Yamamoto: On the Boolean connectivity problem for Horn relations, Discrete Applied Mathematics 158 (2010) 2024-2030.
  59. E. Boros, V. Gurvich, K. Makino, D. Papp, Acyclic, or totally tight, two-person game forms: Characterization and main properties, Discrete Mathematics 310 (2010) 1135-1151.
  60. E. Boros, K. Elbassioni, K. Makino, Left-to-right multiplication for monotone Boolean dualization, SIAM Journal on Computing 39 (2010) 3424-3439.
  61. T. Ishii, K. Makino, Posi-modular systems with modulotone requirements under permutation constraints, Discrete Mathematics, Algorithms and Applications 2 (2010) 61-76.
  62. E. Boros, K. Elbassioni, V. Gurvich, K. Makino, On effectivity functions of game forms, Games and Economic Behavior 68 (2010) 512-531.
  63. K. Elbassioni, K. Makino, I. Rauf, On the readability of monotone Boolean formulae, Journal of Combinatorial Optimization 22 (2010).
  64. H. A. Harutyunyan, A. L. Liestman, K. Makino, T. C. Shermer, Nonadaptive broadcasting in trees, Networks 57 (2011) 157-168.
  65. K. Makino, S. Tamaki, M. Yamamoto, An exact algorithm for the Boolean connectivity problem for k-CNF, Theoretical Computer Science, 412 (2011) 4613-4618.
  66. E. Boros, V. Gurvich, K. Makino, W. Shao, Nash-solvable two-person symmetric cycle game forms, Discrete Applied Mathematics, 159 (2011) 1461-1487.
  67. E. Boros, Y. Crama, P. L. Hammer, T. Ibaraki, A. Kogan, K. Makino, Logical analysis of data: classification with justification, Annals of Operations Research 188 (2011) 33-61.
  68. A. Elmasry, K. Elbassioni, K. Makino, Finding simplices containing the origin in two and three dimensions, to appear in International Journal of Computational Geometry and Applications.
  69. X. Han, K. Makino, Online removable knapsack with limited cuts, to appear in Theoretical Computer Science.
  70. K. Makino, H. Ono, Deductive Inference for the Interiors and Exteriors of Horn Theories, to appear in ACM Transactions on Computational Logic.
  71. M. Chrobak, G. Woeginger, K. Makino, H. Xu, Caching is hard - even in the fault model, to appear in Algorithmica.

Papers in Reviewed Conferences, Symposia and Workshops

  1. K. Makino and T. Ibaraki, The maximum latency and identification of positive Boolean functions, ISAAC'94 Algorithms and Computation}, edited by D. Z. Du and X. S. Zhang, Springer Lecture Notes in Computer Science, 834 (1994) 324-332.
  2. K. Makino and T. Ibaraki, A fast and simple algorithm for identifying 2-monotonic positive Boolean functions, ISAAC'95 Algorithms and Computation, edited by J. Staples et al., Springer Lecture Notes in Computer Science, 1004 (1995) 291-300.
  3. E. Boros, T. Ibaraki and K. Makino, Boolean analysis of imcomplete examples, Algorithm Theory -- SWAT'96, edited by R. Karlsson and A. Lingas, Springer Lecture Notes in Computer Science, 1097 (1996) 440-451.
  4. K. Makino, T. Suda, K. Yano, and T. Ibaraki, Data analysis by positive decision trees, Proceedings of International Symposium on Cooperative Database Systems for Advanced Applications (CODAS'96) (1996) 257-263.
  5. E. Boros, T. Ibaraki and K. Makino, Monotone extensions of Boolean data sets, Algorithmic Learning Theory ALT'97, edited by M. Li and A. Maruoka, Springer Lecture Notes in Artifical Intelligence, 1316 (1997) 161-175.
  6. T. Eiter, T. Ibaraki and K. Makino, Two-face Horn extensions, ISAAC'97 Algorithms and Computation, edited by H. W. Leong et al., Springer Lecture Notes in Computer Science, 1350 (1997) 112-121.
  7. T. Eiter, T. Ibaraki and K. Makino, On disguised double Horn functions and extensions, STACS'98, edited by M. Morvan et al., Springer Lecture Notes in Computer Science, 1373 (1997) 50-60.
  8. A. Kogan, T. Ibaraki and K. Makino, Functional dependencies in Horn theories, Proceedings of Fifth International Symposium on Artificial Intelligence and Mathematics.
  9. T. Eiter, T. Ibaraki and K. Makino, Computing intersections of Horn theories for reasoning with models, Proceedings of AAAI'98, (1998), 292-297.
  10. T. Eiter, T. Ibaraki and K. Makino, Disjunctions of Horn theories and their cores, ISAAC'98, edited by K.-Y. Chwa and O. H. Ibarra, Taejon (Korea), Springer Lecture Notes in Computer Science 1533 (1998) 49-58.
  11. T. Eiter, T. Ibaraki and K. Makino, On the Difference of Horn theories, STACS'99, edited by Meinel et al., Trier (Germany), Springer Lecture Notes in Computer Science 1563, (1999) 467-477.
  12. K. Makino, T. Ono and T. Ibaraki, Interior and exterior functions of positive Boolean functions, Proceedings of the 1st Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Kyoto (Japan), 1999, 159-166.
  13. K. Makino, Y. Uno and T. Ibaraki, On minimum edge ranking spanning trees, in MFCS'99, edited by M. Kutylowski et al., Szklarska Poreba (Poland), Springer Lecture Notes in Computer Science 1672, (1999) 398-409.
  14. K. Makino, A linear time algorithm for recognizing regular Boolean functions, ISAAC'99, edited by A. Aggarwal and C.~P. Rangan, Chennai (India), Springer Lecture Notes in Computer Science 1741, (1999) 259-268.
  15. K. Makino and T. Kameda, Efficient generation of all regular non-dominated coteries, Proceedings of PODC2000, 279-288, Portland (USA), 2000.
  16. E. Boros, V. Gurvich, L. Khachiyan and K. Makino, Generating partial and multiple transversals of a hypergraph, ICALP2000, edited by U. Montanari et al., Geneva (Switzerland), Springer Lecture Notes in Computer Science 1853, (2000) 588-599.
  17. K. Makino, M. Yamashita and T. Kameda, Max- and min-neighborhood monopolies, SWAT2000, edited by M. M. Halldorsson, Bergen (Norway), Springer Lecture Notes in Computer Science 1851, (2000) 513-526.
  18. K. Arata, S. Iwata, K. Makino and S Fujishige, Locating sources to meet flow demands in undirected networks, SWAT2000, edited by M. M. Halldorsson, Bergen (Norway), Springer Lecture Notes in Computer Science 1851, (2000) 300-313.
  19. H. Ono, K. Makino and T. Ibaraki, Logical analysis of data with decomposable structures, COCOON2000, edited by D.-Z. Du et al., Sydney (Australia), Springer Lecture Notes in Computer Science 1858, (2000) 396-406.
  20. E. Boros, T. Ibaraki and K. Makino, Fully consistent extensions of partially defined Boolean functions with missing bits, IFIP TCS2000, edited by J. van Leeuwen et al., Sendai (Japan), Springer Lecture Notes in Computer Science 1872, (2000) 257-272.
  21. E. Boros, T. Horiyama, T. Ibaraki, K. Makino and M. Yagiura, Finding essential attributes in binary data, IDEAL2000 (International Conference on Intelligent Data Engineering and Automated Learning), edited by K. Sak Leung et al., Hong Kong, Springer Lecture Notes in Computer Science 1983, (2000) 133-138.
  22. E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan and K. Makino, On generating all minimal integer solutions for a monotone system of linear inequalities, ICALP 2001, edited by F. Orejas et al., Crete (Greece), Springer Lecture Notes in Computer Science 2076, (2001) 92-103.
  23. E. Boros, V. Gurvich, L. Khachiyan and K. Makino, Generating weighted transversals of a hypergraph, Proceedings of the 2nd Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, edited by A. Frank, G.Y. Katona, A. Recski, Budapest (Hungary), April 20-23, 2001, 13-23.
  24. H. Ito, K. Makino, K. Arata, Y. Itatsu, S. Fujishige, Source Location Problem with Edge-Connectivity Requirements in Digraphs, Proceedings of the 2nd Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, edited by A. Frank, G.Y. Katona, A. Recski, Budapest (Hungary), April 20-23, 2001, 92-97.
  25. Bert Randerath, Ewald Speckenmeyer, Endre Boros, Peter Hammer, Alex Kogan, Kazuhisa Makino, Bruno Simeone, Ondrej Cepek, A Satisfiability Formulation of Problems on Level Graphs, Proceedings of SAT 2001: Workshop on Theory and Applications of Satisfiability Testing, June, 2001.
  26. E. Boros, V. Gurvich, L. Khachiyan and K. Makino, On the complexity of generating maximal frequent and minimal infrequent sets, STACS 2002, edited by H. Alt and A. Ferreira, Antibes - Juan les Pins (France), Springer Lecture Notes in Computer Science 2285, (2002) 133-141.
  27. T. Eiter, G. Gottlob, K. Makino, New Results on Monotone Dualization and Generating Hypergraph Transversals, Annual ACM Symposium on Theory of Computing (STOC 2002), Montreal (Canada), 14-22, 2002.
  28. T. Eiter, K. Makino, On Computing all Abductive Explanations, AAAI-2002, Edmonton (Canada), 62-67, 2002.
  29. K. Makino, Y. Uno, T. Ibaraki, Minimum edge ranking spanning trees of threshold graphs, ISAAC 2002, edited by Prosenjit Bose and Pat Morin, Lecture Notes in Computer Science 2518 (2002) 428-440.
  30. E Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, K. Makino, An intersection inequality for discrete distributions and related generation problems, ICALP 2003, edited by J. C. M. Baeten et al., Eindhoven (The Netherlands), Lecture Notes in Computer Science 2719 (2003) 543-555.
  31. T. Eiter, K. Makino, Generating all Abductive Explanations for Queries on Propositional Horn Theories, Computer Science Logic 2003 (CSL 03), edited by M. Baaz and J. A. Makowsky, Vienna (Austria), Lecture Notes in Computer Science 2803 (2003) 197-211.
  32. T. Eiter, K. Makino, Abduction and the Dualization Problem, Discovery Science (DS 2003), edited by G. Grieser et al., Sapporo (Japan), Lecture Notes in Artificial Intelligence 2843 (2003) 1-20.
  33. S. Mamada, K. Makino, S.Fujishige, The evacuation problem in tree dynamic networks with multiple exits, International Symposium on Systems & Human Science for Safety, Security, and Dependability 2003 (SSR2003), (2003) 347-351.
  34. Y. Asahiro, T. Horiyama, K. Makino, H. Ono, T. Sakuma, and M. Yamashita, How to Collect Balls Moving in the Euclidean Plane Proc. Computing: The Australasian Theory Symposium (CATS), pp.1-16, Jan. 2004.
  35. K. Makino, T. Uno, New algorithms for enumerating all maximal cliques, Algorithm Theory -- SWAT 2004, edited by T. Hagerup and J. Katajainen, Humlebaek (Denmark), Lecture Notes in Computer Science 3111 (2004) 260-272.
  36. E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, K. Makino, Generating paths and cuts in multi-pole (di)graphs, MFCS 2004, edited by J. Fiala et al., Prague (Czech Republic), Lecture Notes in Computer Science 3153 (2004) 298-309.
  37. S. Mamada, T. Uno, K. Makino, S. Fujishige, An O(n log^2 n) algorithm for the optimal sink location problem in dynamic tree networks, Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004), edited by J.-J. Lvy et al., Toulouse (France) Kluwer, (2004) 251-264.
  38. S. Mamada, K. Makino and S. Fujishige, A polynomial time algorithm for the two-sink location problem in a tree dynamic network. Proceedings of the 2nd International Symposium on Systems & Human Science, San Francisco, USA, 2005.
  39. M. Sakashita, K. Makino, S. Fujishige, Minimizing a monotone concave function with laminar covering constraints, ISAAC 2005, edited by X. Deng and D.-Z. Du, Hainan (China), Lecture Notes in Computer Science 3827 (2005) 71-81.
  40. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, K. Makino, Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs, ISAAC 2005, edited by X. Deng and D.-Z. Du, Hainan (China), Lecture Notes in Computer Science 3827 (2005) 156-165.
  41. M. Sakashita, K. Makino, S. Fujishige, Laminar covering problem, The 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest (Hungary), 2005.
  42. M. Sakashita, K. Makino, S. Fujishige, Minimum Cost Source Location Problems with Flow Requirements, LATIN 2006, edited by J. R. Correa et al., Valdivia (Chile), Lecture Notes in Computer Science 3887 (2006) 769-780.
  43. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, K. Makino, Enumerating spanning and connected subsets in graphs and matroids, ESA 2006, edited by Y. Azar and T. Erlebach, Zurich (Switzerland), Lecture Notes in Computer Science 4168 (2006) 444-455.
  44. M. Sakashita, K. Makino, H. NagamochiS. Fujishige, Minimum transversals in posi-modular systems, ESA 2006, edited by Y. Azar and T. Erlebach, Zurich (Switzerland), Lecture Notes in Computer Science 4168 (2006) 576-587.
  45. K. Makino, S. Tamaki, M. Yamamoto, On the Boolean connectivity problem for Horn relations, SAT 2007, edited by J. Marques-Silva and K. A. Sakallah, Lisbon (Portugal), Lecture Notes in Computer Science 4501 (2007) 187-200.
  46. A. Elmasry, K. Makino, Finding intersections of bichromatic segments defined by points, CCCG 2007, edited by P. Bose, Ottawa (Canada), 269-272.
  47. E. Boros, K. Borys, K. M. Elbassioni, V. Gurvich, K.Makino, G. Rudolf, Generating minimal k-vertex connected spanning subgraphs, COCOON 2007, edited by G. Lin, Banff (Canada), Lecture Notes in Computer Science 4598 (2007) 222-231.
  48. D. Gaur, K. Makino: On the fractional chromatic number of monotone self-dual Boolean functions, FAW 2007, edited by F. Preparata and Q. Fang, Lanzhou (China), Lecture Notes in Computer Science 4613 (2007) 148-159.
  49. E. Boros, K. Elbassioni, Vl. Gurvich, K. Makino, V. Oudalov, A complete characterization of Nash-solvability of bimatrix games in terms of the exclusion of Certain 2X2 subgames, CSR 2008, edited by E. A. Hirsch et al., Moscow (Russia), Lecture Notes in Computer Science 5010 (2008) 99-109.
  50. T. Eiter, K. Makino: New results for Horn cores and envelopes of Horn disjunctions, ECAI 2008, edited by M. Ghallab et al., Patras (Greece), 60-64.
  51. E. Boros, K. Elbassioni, K. Makino, On Berge multiplication for monotone Boolean dualization, ICALP 2008, edited by L. Aceto et al., Reykjavik (Iceland), Lecture Notes in Computer Science 5125 (2008) 48-59.
  52. K. Makino, H. Ono:, Deductive inference for the interiors and exteriors of Horn theories, ISAAC 2008, edited by S.-H. Hong, H. Nagamochi, and T. Fukunaga, Gold Coast (Australia), Lecture Notes in Computer Science 5369 (2008) 390-401.
  53. T. Ishii, K. Makino, Augmenting edge-connectivity between vertex subsets, CATS 2009, Wellington (New Zealand), 2009, 45-51.
  54. K. Elbassioni, K. Makino, I. Rauf, On the readability of monotone Boolean formulae, COCOON 2009, edited by H. Q. Ngo, Niagara Falls (USA), Lecture Notes in Computer Science 5609 (2009) 496-505.
  55. K. Elbassioni, K. Makino, I. Rauf, Output-sensitive algorithms for enumerating minimal transversals for some geometric hypergraphs, ESA 2009, edited by A. Fiat and P. Sanders, Copenhagen (Denmark), Lecture Notes in Computer Science 5757 (2009) 143-154.
  56. E. Boros, K. Makino. A fast and simple parallel algorithm for the monotone duality problem, ICALP 2009, edited by S. Albers et al., Rhodes (Greece), Lecture Notes in Computer Science 5555 (2009) 183-194.
  57. X. Han, K. Makino, Online knapsack problems with limited cuts, ISAAC 2009, edited by Y. Dong et al., Hawaii (USA), Lecture Notes in Computer Science 5878 (2009) 341-351
  58. T. Ishii, K. Makino, Posi-modular systems with modulotone requirements under permutation constraints, ISAAC 2009, edited by Y. Dong et al., Hawaii (USA), Lecture Notes in Computer Science 5878 (2009) 473-482.
  59. X. Han, K. Makino, Online minimization knapsack problem, WAOA 2009, edited by E. Bampis and K. Jansen, Copenhagen (Denmark), Lecture Notes in Computer Science 5893 (2009) 182-193.
  60. E. Boros, K. Elbassioni, K. Makino, Berge multiplication for monotone Boolean dualization, The 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest (Hungary), 2009.
  61. M. Chrobak, G. Woeginger, K. Makino, H. Xu, Caching is hard - even in the fault model, ESA 2010, edited by M. de Berg and U. Meyer, Liverpool (UK), Lecture Notes in Computer Science 6346 (2010) 195-206.
  62. R. Fujita, Y. Kobayashi, K. Makino, Robust matchings and matroid intersections, ESA 2010, edited by M. de Berg and U. Meyer, Liverpool (UK), Lecture Notes in Computer Science 6347 (2010) 123-134.
  63. E. Boros, K. Elbassioni, V. Gurvich, K. Makino, A pumping algorithm for ergodic stochastic mean payoff games with perfect information, IPCO 2010, edited by F. Eisenbrand and F. B. Shepherd, Lausanne (Switzerland), Lecture Notes in Computer Science 6080 (2010) 341-354.
  64. K. Makino, S. Tamaki, M. Yamamoto, An exact algorithm for the Boolean connectivity problem for k-CNF, SAT 2010, edited by O. Strichman and S. Szeider, Edinburgh (UK), Lecture Notes in Computer Science 6175 (2010) 172-180.
  65. N. Kakimura, K. Makino, Robust independence systems, ICALP 2011, edited by L. Aceto et al., Zurich (Switzerland), Lecture Notes in Computer Science 6755 (2011) 367-378.
  66. E. Boros, K. Elbassioni, M. Fouz, V. Gurvich, K. Makino, B. Manthey, Stochastic mean payoff games: Smoothed analysis and approximation schemes, ICALP 2011, edited by L. Aceto et al., Zurich (Switzerland), Lecture Notes in Computer Science 6755 (2011) 147-158.
  67. N. Kakimura, K. Makino, Robust independence systems, The 7th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Kyoto (Japan), 2011.
  68. K. Makino, S. Tamaki, M. Yamamoto, Derandomizing HSSW Algorithm for 3-SAT, to appear in COCOON 2011, Dallas (USA), 2011.

Others

  1. H. Ono, K. Makino and T. Ibaraki, Logical analysis of data by decomposable Boolean functions, Advanced Database Systems for Integration of Media and User Environments'98, edited by Y. Kambayashi, et al., World Scientific, Singapore, pp.29-34, 1998
  2. S. Mamada, K. Makino, S.Fujishige, An evacuation problem in tree dynamic networks with multiple exits, Systems and Human Science, Elsevier, pp. 517-526, 2005.

Selected Reports and Manuscripts

  1. E. Boros, T. Ibaraki and K. Makino, Extensions of partially defined Boolean functions with missing data, RUTCOR Research Report RRR 6-96, Rutgers University 1996.
  2. T. Eiter, T. Ibaraki and K. Makino, Multi-face Horn functions, Technical Report CD-TR 96/95, Christial Doppler Labor f\"{u}r Expertensysteme, Technische Universit\"{a}t Wien, June 1996.
  3. E. Boros, O. Cepek, P. L. Hammer, A. Kogan, K. Makino, B. Randerath, B. Simeone and E. Speckenmeyer, A Satisfiability Formulation of Problems on Level Graphs, RUTCOR Research Report RRR 40-2001, Rutgers University, 2001.
Return to home page of Kaz Makino