CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017


On (distance) Laplacian energy and (distance) signless Laplacian energy of graphs  [PDF]

The energy $\mathcal{E}(G)$ of a simple graph $G$ is the sum of absolute values of the eigenvalues of its adjacency matrix. The Laplacian energy, the signless Laplacian energy and the distance energy of graph $G$ are denoted by $LE(G)$, $SLE(G)$ and $DE(G)$, respectively. This talk is about distance Laplacian energy $DLE$ and distance signless Laplacian energy $DSLE$ of a connected graph. We give lower bounds on distance Laplacian energy $DLE$ in terms of order $n$ for graphs and trees, and characterize the corresponding extremal graphs. Also, we discuss some relationships between $DE$, $DSLE$ and $DLE$ of connected graph $G$.

YU HIN (GARY) AU, Milwaukee School of Engineering
On Strong Lift-and-Project Operators versus Chipped and Cropped Hypercubes  [PDF]

In this talk, we focus on several semidefinite-optimization-based lift-and-project operators, including operators due to Lasserre and variants of the Sherali-Adams and Bienstock-Zuckerberg operators. We study their performance on some elementary polytopes -- hypercubes that are chipped (at least one vertex of the hypercube removed by intersection with a closed halfspace) or cropped (all $2^n$ vertices of the hypercube removed by intersection with $2^n$ closed halfspaces) to varying degrees of severity $\rho$, and prove bounds on $\rho$ where these operators would perform badly on the aforementioned examples. We also show that the integrality gap of the chipped hypercube is invariant under the application of several lift-and-project operators of varying strengths.

This is joint work with Levent Tunçel from the University of Waterloo.

AHMED-SAHER AZIZI-SULTAN, Taibah University, Madinah-Munawara, Saudi Arabia
The First Logmatic SAT Solver  [PDF]

SAT is an important but NP-complete problem. Most SAT solvers are based on Davis-Putnam-Logemann-Loveland (DPLL) algorithm which is a blind branch and backtrack technique that explores the search space exhaustively until a solution is found, resulting in an excessive time complexity. Some enhancement was made possible by equipping the DPLL algorithm with pruning techniques such as backjumping, conflict-driven lemma learning, and restarts. However, the major drawback of having blind control over the search area remains. In contrast, the Logmatic approach combines techniques from logic and math, enabling one of scanning the search tree and detecting efficiently the branches that possibly contain solutions. Thus it suffices to consider only these branches rather than the entire search tree, reducing considerably the amount of calculation time. Comparing the Logmatic solver with Riss (one of the best SAT solvers), significant improvements were reported for all the tested instances of SAT problem.

STEPHEN GISMONDI, University of Guelph
Novel Use of Matching That Sometimes Detects Infeasible IPs  [PDF]

A novel matching-based heuristic algorithm that detects an infeasible $\{0,1\}$ IP is presented. Input to the algorithm is a set of nested doubly stochastic subsystems and a set of instance defining variables set at zero level. Output from the algorithm is either a certificate of infeasibility, or an undecided IP with a non-empty set of variables deduced to be at zero level. All feasible IPs, and all infeasible IPs that fail to be detected infeasible are undecided. Results of an application to a model of the Hamilton tour decision problem are presented followed by models of both the graph and subgraph isomorphism decision problems. The algorithm is easy to generalize and highly parallel. It's proposed for use in search based algorithms/solvers, in concert with other search techniques.

GEORGE MANOUSSAKIS, Université Paris Saclay
Minkowski Sums : Diameters and Holes  [PDF]

We investigate a family of Minkowski sums of integer vector associated to graphs. We show that this family yields a lower bound for the largest edge-graph diameter of the convex hull of integer-valued points. The lower bound is obtained via classical results concerning the number of disjoint perfect matchings of the complete graph. We discuss the problem of finding holes in a Minkowski sum of integer vectors; that is, whether there exists or not an integer-valued point in the Minkowski sum which cannot be expressed as a subsum of the integer vectors generating the Minkowski sum. This problem is related to a question dealing with the convex hull of degree sequences of k-uniform hyper graphs. Related complexity questions are also presented.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology