The 10th Haifa Workshop

on Interdisciplinary Applications of Graphs,

Combinatorics and Algorithms

23-25 May 2010, Haifa (Israel)

Uri Natan Peled
In memory of  Uri Natan Peled, ז"ל


How to get here

Registration

Abstracts Schedule

Call For Papers

Main


 

1stday , 2ndday , 3rdday

Location

  • May 23 morning, Room 570, Education Building.
  • May 23 afternoon, Safdie Auditorium, Multi-purpose Building.
  • May 24 all day, Room 570, Education Building.
  • May 25 Excursion.

Program

 

Sunday May 23, 2010

09:00

Registration and Greetings

 

09:30

Seffi Naor (Technion, Israel)

 

 

Online Algorithms, Linear Programming, and the k-Server Problem

10:15

Break

 

10:30

Session 1

Session 2

10:30

Mark Korenblit (HIT, Israel)

Shiri Chechik (Weizmann Institute, Israel)

The decomposition method for generating algebraic expressions of square rhomboids

Forbidden-Set distance labels for graphs
of bounded doubling dimension

10:55

Nathan Keller (Weizmann Institute, Israel)

Oren Ben-Zwi (Univ. of Haifa, Israel)

A tight quantitative version of Arrow's impossibility theorem

A hat trick

11:20

Yefim Dinitz (Ben-Gurion Univ., Israel)

Rami Puzis (Ben-Gurion Univ., Israel)

Hybrid Bellman-Ford-Dijkstra algorithm

Expressing centrality in terms of routing betweeness

11:45

Break

 

12:00

Session 3

Session 4

12:00

Noam Goldberg (Technion, Israel)

Yuval Emek (Tel-Aviv Univ., Israel)

Sparse weighted voting classifier selection and its LP relaxation

Sparse reliable graph backbones

12:25

Eugene Levener (HIT & Bar-Ilan Univ., Israel)

Michael Borokhovich (Ben-Gurion Univ., Israel)

 

A fully polynomial algorithm for a cyclic scheduling problem on graphs with interval data

Tight bounds for algebraic gossip on graphs

12:50

Lunch

 

 

Remembering Uri N. Peled

 

14:00

Bill Cunningham (Univ. of Waterloo, Canada)

 

Split decomposition

 

14:45

Gyorgy Turan (Univ. of Illinois at Chicago and Univ. of Szeged)

Horn formulas - a survey of recent results

 

15:30

Break

 

16:00-18:30

Memorial Session - Safdie Auditorium, Multi-Purpose Building locate here

Chairs: Martin Golumbic and Dan Peled

 

Messages from friends and family; the Mathematics of Uri Natan Peled

General Lectures:

 

Hon. Zvi Tal (former Justice of the Supreme Court, Israel) (uncle)

Reflections on Human Dignity

הרהורים על כבוד האדם

Jonathan (Tsoni) Peled (Albert Einstein College of Medicine, Yeshiva Univ., USA) (son)

Studies on Lymphoma Tumors of Mice as a Model for Human Non-Hodgkin's Lymphoma

Elana Zion-Golumbic (Columbia Univ. Medical Center & Nathan Kline Inst. for Psych. Research, USA)

Selective attention at a cocktail party: Insights from  intracranial EEG in humans

 

Monday May 24, 2010

09:00

Registration, Tea and Coffee

 

09:30

Ronitt Rubinfeld (Tel-Aviv Univ., Israel and MIT, USA)

 

Maintaining a large matching or a small vertex cover

10:15

Break

 

10:30-11:45

Session 5

Session 6

10:30

Yahav Nussbaum (Tel-Aviv Univ., Israel)

Tomer Kotek (Technion, Israel)

Linear-time recognition of probe interval graphs

A representation theorem for holonomic sequences

10:55

George Mertzios (Technion, Israel)

Alexander Zadorojniy (Tel Aviv Univ,Israel)

Recent results on tolerance graphs and related classes

A new pivoting rule for the simplex algorithm

11:20

Eliah Ninyo (Univ. of Haifa, Israel)

Yona Cherniavsky (Ariel Univ. Center of Samaria, Israel)

Characterization of alternately orientable graphs that are weakly-chordal

Weighted Coxeter graphs, geometric representation and generalized numbers game

11:45

Break

 

12:00

Fedor Fomin (Univ. of Bergen, Norway)

Kernelization

 

12:50

Lunch -- Caesarea Rothschild Institute, 6th floor

14:00

Alek Vainstein (Univ. of Haifa, Israel)

Geometry of planar directed trivalent networks

14:45

Michael Elkin (Ben-Gurion Univ., Israel)

Distributed deterministic graph coloring

 

15:30

Break

 

15:45-17:00

Session 7

Session 8

15:45

Allan Borodin (Univ. of Toronto, Canada)

David Tankus (Ariel Univ. Center of Samaria, Israel)

On sum coloring for restricted families of graphs

Well-covered graphs without C4, C6 and C7

16:10

Panagiotis Cheilaris (Ben-Gurion Univ., Israel)

Yulia Kempner (Holon Institute of Technology, Israel)

Graph unique-maximum and conflict-free colorings

Poly-dimension of antimatroids

16:35

Moti Medina (Tel-Aviv Univ., Israel)

Vadim Levit (Ariel Univ. Center of Samaria, Israel)

An O(log n)-competitive online centralized randomized packet-routing algorithms for lines

On the independence polynomial of a threshold graph

17:10-18:30

Session 9

Session 10

17:10

Irith Ben-Arroyo Hartman (Int'l. Institute for Information Technology, Bangalore, India)

Yelena Yuditsky (Ben-Gurion Univ., Israel)

Contractors' minimum spanning tree

Polychromatic coloring for half-planes

17:35

Eyal Ackerman (Univ. of Haifa at Oranim, Israel)

Amir Sapir (Sapir College, Israel)

On the number of edges in graphs with orthogonal  crossings

Which multi-peg tower of hanoi problems are exponential?

18:00

Oren Weimann (Weizmann Institute, Israel)

Replacement paths via fast matrix multiplication

19:00

Dinner

 

 

 

Tuesday 25, 2010

9:30

Informal scientific discussions

 

12:00

Excursion