MPI-INF Logo

MPI-INF D1 Publications

Search the publication database
.
Return

Your search returned the following 33 documents:

  1. Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Discrete Applied Mathematics 156 (11): 2020-2034, 2008
  2. Generating All Vertices of a Polyhedron Is Hard
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich
    Discrete & Computational Geometry 39 (1-3): 174-190, 2008
  3. Generating Cut Conjunctions in Graphs and Related Problems
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Algorithmica 51 (3): 239-263, 2008
  4. On Enumerating Minimal Dicuts and Strongly Connected Subgraphs
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Algorithmica 50 (1): 159-172, 2008
  5. On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf, and Jihui Zhao
    Theory Comput. Syst. 43 (2): 204-233, 2008
  6. A global parallel algorithm for the hypergraph transversal problem
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Information Processing Letters 101 (4): 148-155, 2007
  7. Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Theoretical Computer Science 379 (3): 361-376, 2007
  8. Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Discrete Applied Mathematics 155 (2): 137-149, 2007
  9. On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Theoretical Computer Science 382 (2): 139-150, 2007
  10. Enumerating Spanning and Connected Subsets in Graphs and Matroids
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    In: Algorithms - ESA 2006, 14th Annual European Symposium, Z├╝rich, Switzerland, 2006, 444-455
  11. Generating All Vertices of a Polyhedron is Hard
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06, Miami, FL, USA, 2006, 758-765
  12. A New Algorithm for the Hypergraph Transversal Problem
    Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Computing and combinatorics : 11th Annual International Conference, COCOON 2005, Kunming, China, 2005, 767-776
  13. Generating All Minimal Integral Solutions to Monotone $\wedge,\vee$-Systems of Linear, Transversal and Polymatroid Inequalities
    Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Mathematical Foundations of Computer Science 2005 : 30th International Symposium, MFCS 2005, Gdansk, Poland, 2005, 556-567
  14. Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Algorithms and computation : 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, 2005, 156-165
  15. On the Complexity of Some Enumeration Problems for Matroids
    Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    SIAM Journal on Discrete Mathematics 19 (4): 966-984, 2005
  16. An Efficient Implementation of a Joint Generation Algorithm
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: Experimental and efficient algorithms : Third International Workshop, WEA 2004, Angra dos Reis, Brazil, 2004, 114-128
    [PDF: Download: WAE04.pdf]
  17. Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: Integer programming and combinatorial optimization : 10th International IPCO Conference, New York, NY, USA, 2004, 152-162
    [PDF: Download: IPCO04.pdf]
  18. Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, 2004, 488-498
    [PDF: Download: LATIN04.pdf]
  19. Generating Paths and Cuts in Multi-pole (Di)graphs
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino
    In: Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004, Prague, Czech Republic, 2004, 298-309
    [PDF: Download: MFCS04.pdf]
  20. Algorithms for Enumerating Circuits in Matroids.
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, 2003, 485-494
    [PDF: Download: ISAAC2003.pdf]
  21. An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    In: Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, 2003, 556-567
    [PDF: Download: ESA03.pdf]
  22. An Inequality for Polymatroid Functions and its Applications
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Discrete Applied mathematics 131: 27 p., 2003

  23. An Intersection Inequality for Discrete Distributions and Related Generation Problems
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino
    In: Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, 2003, 543-555
    [PDF: Download: ICALP03.pdf]
  24. Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Mathematical Programming, Ser. B 98 (1-3): 14 p., 2003

  25. Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, Vladimir Gurvich, and Kazuhisa Makino
    SIAM Journal on Computing 31: 20 p., 2002

  26. Generating Dual-Bounded Hypergraphs
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Optimization Methods and Software 17 (5): 33 p., 2002
    [PS: Download: oms.ps]
  27. Generating Dual-Bounded Hypergraphs
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Optimization Methods and Software 17 (5): 33 p., 2002
    [PS: Download: oms.ps]
  28. Matroid Intersections, Polymatroid Inequalities, and Related Problems
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    In: Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, 2002, 143-154
    [PDF: Download: MFCS02.pdf]
  29. On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, Vladimir Gurvich, and Kazuhisa Makino
    In: Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Heraklion, Crete, Greece, 2001, 92-103
    [PDF: Download: icalp01.pdf]
  30. An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Parallel Processing Letters 10 (4): 14 p., 2000

  31. Integer optimization on convex semialgebraic sets
    Leonid Khachiyan and Lorant Porkolab
    Discrete & Computational Geometry 23 (2): 207-224, 2000
  32. On the Complexity of Dualization of Monotone Disjunctive Normal Forms
    Michael Fredman and Leonid Khachiyan
    J. Algorithms 21 (3): 618-628, 1996
  33. Computing Integral Points in Convex Semi-algebraic Sets
    Lorant Porkolab and Leonid Khachiyan
    In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS-97), Miami Beach, Florida, USA, October 20-22, 1997, 162-171