Page > 1

TBA

Discrete Structures and Algorithms (Seminar)

by Paul Leopardi

Institution: The University of Melbourne and Australian Government - Bureau of Meteorology

Date: 05/10/2017 11:00am

Abstract: TBA

TBA

Discrete Structures and Algorithms (Seminar)

by Marcus Gordon Volz

Institution: The University of Melbourne

Date: 21/09/2017 11:00am

Abstract: TBA

TBA

Discrete Structures and Algorithms (Seminar)

Institution: The University of Melbourne

Date: 07/09/2017 11:00am

Abstract: TBA

On Aharoni-Berger's conjecture of rainbow matchings

Discrete Structures and Algorithms (Seminar)

by Jane Gao

Institution: Monash University

Date: 24/08/2017 11:00am

Abstract: Let $$G$$ be a properly edge coloured multigraph with $$m$$ colours and let $${\mathcal M}=\{M_1,\ldots, M_m\}$$ be the set of $$m$$ matchings induced by each colour in $$G$$. Assume that every matching in $${\mathcal M}$$ has size $$n$$. Aharoni and Berger conjectured that if $$G$$ is bipartite and $$m=n-1$$ then $$G$$ contains a full rainbow matching, i.e. a matching that contains exactly one edge from each $$M_i$$ for each $$1\le i\le m$$. We prove an approximate version of this conjecture. We show that if $$m\le n-n^{c}$$, where $$c>9/10$$, and $$G$$ is simple whereas not necessarily bipartite, then $$G$$ contains a rainbow matching if $$n$$ is sufficiently large. Our proof proceeds by analysing a randomised algorithm. This is collaborated work with Reshma Ramadurai, Ian Wanless and Nick Wormald.

A modified Benders method for the single and multiple allocation p-hub median problem

Discrete Structures and Algorithms (Seminar)

by Hamid Mokhtar

Institution: Monash University

Date: 10/08/2017 11:00am

Abstract: We consider the well-known uncapacitated p-hub median problem with multiple allocation (UMApHMP), and single allocation (USApHMP). These problems have received significant attention in the literature because while they are easy to state and understand, they are hard to solve. They also find practical applications in logistics and telecommunication network design. Due to the inherent complexity of these problems, we apply a modified Benders decomposition method to solve large instances of the UMApHMP and USApHMP. The Benders decomposition approach does, however, suffer from slow convergence mainly due to the high degeneracy of subproblems. To resolve this, we apply a novel method of accelerating Benders Method. Our approach outperforms existing results in the literature by more appropriately choosing parameters for the accelerated Benders method, and by solving subproblems more efficiently using minimum cost network flow algorithms. We implement our approach on well-known benchmark data sets in the literature and compare our computational results with existing results. The computational results confirms that our approach is efficient and enables us to solve larger single- and multiple allocation hub median instances.

Hybrid optimisation of vehicle routing problems

Discrete Structures and Algorithms (Seminar)

by Edward Lam

Institution: The University of Melbourne

Date: 01/06/2017 10:00am

Abstract: We propose a hybrid optimisation method, named Branch-and-Check with Explanations (BCE), that integrates linear programming (LP), constraint programming (CP), and Boolean satisfiability (SAT). BCE features an LP master problem that omits several families of cuts, and a CP subproblem that implements all omitted cuts as constraint propagators. Objective bounds and linear relaxation solutions are computed using the master problem, and then checked by the CP subproblem for feasibility of the omitted constraints. Infeasible solutions are sent to a SAT solver, which performs conflict analysis to derive nogoods. The nogoods are seamlessly translated into cuts for both the LP and CP problems. Experimental results for the Vehicle Routing Problem with Time Windows show that BCE dominates a branch-and-cut model even though it uses general-purpose conflict analysis rather than specialised separation algorithms to generate cuts.

Vertex-transitive graphs with given arc-type

Discrete Structures and Algorithms (Seminar)

by Nemanja Poznanovic

Institution: The University of Melbourne

Date: 25/05/2017 11:00am

Abstract: Vertex-transitive graphs play a central role in algebraic graph theory. We will begin this talk by discussing some basic properties of these graphs and explaining how they may be classified using the language of arc-types. The arc-type of a vertex-transitive graph is a partition of the graph's valency written as a sum of the lengths of the orbits of a vertex-stabilizer acting on the neighbourhood of that vertex. Parentheses are used in the partition to denote paired orbits. A natural question which arises is which integer partitions (marked with parentheses) occur as the arc-type of some vertex-transitive graph. It has been shown by Conder, Pisanski and Zitnik that every marked integer partition except for 2 = 1+1 and 2 = (1+1) is the arc-type of some vertex-transitive graph. Recently, we have extended this result by showing that every marked integer partition except for 1, 1+1 and (1+1) is the arc-type of infinitely many connected Cayley graphs. We will discuss both of these results and some consequences. No prior knowledge of vertex-transitive graphs is assumed.

A study of cores of vertex-transitive graphs

Discrete Structures and Algorithms (Seminar)

by Bi Wei

Institution: The University of Melbourne

Date: 18/05/2017 11:00am

Abstract: A homomorphism from a graph G to a graph H is a map from V(G) to V(H) such that every edge of G is mapped to an edge of H. A bijective homomorphism from a graph to itself is an automorphism of the graph. A graph is vertex-transitive if any vertex can be mapped to any other vertex by an automorphism. If H is an induced subgraph of G with minimum number of vertices such that there exists a homomorphism from G to H, then H is called a core of G. The core of any graph is unique up to isomorphism. The order of the core of any vertex-transitive graph divides the order of the graph. I will talk about when the vertex set of a vertex-transitive graph can be partitioned into copies of its core. We give a sufficient condition for this to happen.

Are there two non-isomorphic connected graphs that are Ramsey equivalent?

Discrete Structures and Algorithms (Seminar)

by Anita Liebenau

Institution: Monash University

Date: 13/04/2017 11:00am

Abstract: A graph G is Ramsey for a graph H if every 2-colouring of the edges of G contains a monochromatic copy of H (not necessarily induced). Two graphs H and H' are called Ramsey equivalent if every graph G is either Ramsey for both, H and H', or for neither. It may be surprising that the complete graph on k vertices is not Ramsey equivalent to any other connected graph. In fact, we do not know any two connected (non-isomorphic) graphs H and H' that are Ramsey equivalent. In this talk, I will introduce the concept of Ramsey equivalence and show its connections to other questions in Ramsey theory, survey previous results and report on recent progress in the area.

TBA

Discrete Structures and Algorithms (Seminar)

by Joyce Zhang

Institution: The University of Melbourne

Date: 23/03/2017 11:00am

Abstract: Using a stochastic discrete model for urban traffic flow, we study Macroscopic Fundamental Diagrams (MFD) and the cross-correlations between density and flow of arterial road networks. With homogeneously distributed densities, we find a well-defined MFD and a monotonic relation between the cross-correlation and density. The results suggest that the cross-correlation is a natural indicator of traffic phases and vanishes when the network is at capacity. The density spatial heterogeneity has strong impact on the MFD and cross-correlation curve. A case study of perimeter control strategies based on MFD and cross-correlation is conducted. The simulation results suggest that, even with anisotropic traffic demands, both control strategies can improve the network performance in terms of both the traffic flow and density heterogeneity.