Marina Lipshteyn

Research Interests:

Theoretical Computer Science: Graph Theory, Discrete Algorithms, Combinatorial Optimization, Networking.

Industrial Expertise:

Infrastructure of Data Centers, Routing Algorithms, Telecommunication Network Devices, Real-Time Embedded Systems, Network

Management, Grid Computing.

List of Publications:

PAPERS IN REFEREED JOURNALS:

2011:

·         Vertex Intersection Graphs of Paths on a Grid, (with A. Asinowsky, E. Cohen, M.C. Golumbic,  V. Limouzy and M. Stern)

Journal of Graph Algorithms and Applications

2010:

·         Path-bicolorable Graphs, (with A. Brandstadt, M.C. Golumbic and V. B. Le),

Graphs and Combinatorics

2009:

·         Edge Intersection of Single Bend Paths on a Grid, (with M.C. Golumbic and M. Stern),

Networks 54(3), 2009, pp.130-138.

·         Intersection Models of Weakly Chordal Graphs, (with M.C. Golumbic and M. Stern), Discrete Applied Math. 157 (2009) 9, 2031-2047. Postscript

2008:

·         Equivalences and the complete hierarchy of intersection graphs of paths in a tree, (with M.C. Golumbic and M. Stern)

Discrete Applied Mathematics 156 (2008) 17, pp.3203-3215.

·         Representing edge intersection graphs of paths on degree 4 trees, (with M.C. Golumbic and M. Stern),

Discrete Mathematics 308(8)(2008), pp.1381-1387

·         The k-edge intersection graphs of paths in a tree, (with M.C. Golumbic and M. Stern),

Discrete Applied Mathematics 156 (4) 2008, pp. 451-461. Postscript

2007:

·         Recognizing chordal probe graphs and cycle-bicolorable Graphs, (with A. Berry and M.C. Golumbic),

SIAM J. Discrete Math. 21 (2007) 3, 573-591. Postscript

2004:

·         Chordal probe graphs, (with M.C. Golumbic),

Discrete Applied Mathematics 143 (2004), 221-237. Postscript

PAPERS IN REFEREED PROCEEDINGS:

2010:

·         On the bi-enhancement of chordal bipartite probe graphs (with E. Cohen, M.C. Golumbic and M. Stern),

IPL 110 (2010), 193-197. Postscript

2009:

·         Path-bicolorable graphs (extended abstract) (with A. Brandstadt, M.C. Golumbic and V. B. Le),

LNCS 5420, 172-182. Postscript

2008:

·         On The Bi-Enhancement of Chordal-Bipartite Probe Graphs, (with E. Cohen, M.C. Golumbic and M. Stern),

CTW 2008, 152-156. Postscript

·         What is between chordal and weakly chordal graphs? (extended abstract) (with E. Cohen, M.C. Golumbic and M. Stern),

Graph Theoretic Concepts in Computer Science (2008), 275-286.

(Proceedings of WG’08) Postscript

2007:

·         Edge Intersection of Single Bend Paths on a Grid, (with M.C. Golumbic and M. Stern),

CTW 2007, 53-55. Postscript

2006:

·         Finding intersection models of weakly chordal graphs, (with M.C. Golumbic and M. Stern),

Graph Theoretic Concepts in Computer Science (2006), 241-255. (Proceedings of WG’06) Postscript

2005:

·         Representations of edge intersection graphs of paths in a tree, (with M.C. Golumbic and M. Stern),

DMTCS Conference Volume AE (2005), 87-92. (Proceeding of EuroComb’05). Link

2004:

·         Two tricks to triangulate chordal probe graphs in polynomial time, (with A. Berry and M.C. Golumbic),

Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004, 962-969. Postscript

·         The recognition of k-EPT graphs, (with M.C. Golumbic and M. Stern),

Congressus Numerantium 171 (2004), 129-139. Postscript

2003:

·         Chordal probe graphs (extended abstract), (with M.C. Golumbic),

Graph Theoretic Concepts in Computer Science 2880 (2003), 249-260. Postscript

2001:

·         On the hierarchy of interval, probe and tolerance graphs, (with M.C. Golumbic),

Congressus Numerantium 153 (2001), 97-106. Postscript

PAPERS IN PREPARATION OR SUBMITTED:

·         The characterization of alternately orientable graphs that are weakly chordal (with E. Ninyo)

My Ph.D thesis. (2005) Summa Cum Laude.

Patent:

·         Automatic signaling method and device for telecommunication services (with H. Porat) link

Editing:

Teaching:

Some of algorithms I took part in design and implementation in industry:

·         Static Routing Optimization in Ethernet Network: multi-constrain path calculation, optimal multipoint, local and global reshuffling link

·         Ethernet Transport Networks, Architectures of Networking

·         Traffic Aware Routing algorithm in Infiniband network

·         Resource Management in Fabric Management of Ethernet Data Center

Email Contact: