• Arts
• Business
• Computers
• Games
• Health
• Home
• Kids and Teens
• News
• Recreation
• Reference
• Regional
• Science
• Shopping
• Society
• Sports

Open Problems in Graph Algorithms

Please mail me with any corrections, or any other comments. The list is very rough at the moment. Bipartite Classes 1) Chordal Bipartite Graphs The fastest known algorithms for recognizing chordal bipartite graphs involve lexically ordering a matrix, and checking for a forbidden configuration. The checking is linear, and the ordering takes O(mlogn) or O(n^2) time. The ordering algorithm is designed for any matrix, whether or not it has the forbidden configuration. Can you use the fact that the matrices are special to design a linear time algorithm? 2) Find a Geometric Model for Chordal Bipartite Graphs (Spinrad) 3) Bipartite graphs with no induced cycle of length > 6 (Spinrad) Count, recognize, find a good representation of them. 4) Perfect Elimination Bipartite Recognition Perfect elimination bipartite graphs are discussed in Golumbic's book, and correctly model perfect Gaussian elimination in arbitrary matrices. However, the best recognition algorithm for these graphs takes O(n^3) time, and actually performing Gaussian elimination can be done in O(n^3) time. These graphs would seem much more useful if they could be recognized in much less time than performing the elimination. 5) Chordal Bipartite Plus weight condition (Shamir) Must find gamma-free ordering in which for all row/column pairs topleft + bottomright k? The best I can do is O(n^(k-.634)). Can you determine whether a graph has a chordless cycle containing a particular vertex v in linear time? This would allow an O(m^2) algorithm for k = 5. Can you recognize graphs which are "generalized simplicially reducible" efficiently; i.e., graphs which can be reduced to the empty graph by successively removing vertices which are not in the center of a $P sub k$? Is it NP-complete to determine the smallest value $k$ such that $G$ is "$k$-simplicially reducible"? Can you determine whether a pair of vertices is in a common hole of length > 4 in polynomial time? 3) Chi-boundedness of hole-free graphs (Sritharan) Hole free (not

Contact Information