David Avis

  • McGill University, Montreal, Canada

According to our database1, David Avis authored at least 107 papers between 1977 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


Correction to: On Reconfiguration Graphs of Independent Sets Under Token Sliding.
Graphs Comb., August, 2023

On Reconfiguration Graphs of Independent Sets Under Token Sliding.
Graphs Comb., June, 2023

On the foundations and extremal structure of the holographic entropy cone.
Discret. Appl. Math., March, 2023

A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets.
CoRR, 2023

Sparktope: linear programs from algorithms.
Optim. Methods Softw., 2022

On Reconfiguration Graph of Independent Sets under Token Sliding.
CoRR, 2022

mts: a light framework for parallelizing tree search codes.
Optim. Methods Softw., 2021

Algorithmic enumeration of surrounding polygons.
Discret. Appl. Math., 2021

lrsarith: a small fixed/hybrid arithmetic C library.
CoRR, 2021

An Analysis of Budgeted Parallel Search on Conditional Galton-Watson Trees.
Algorithmica, 2020

Compact linear programs for 2SAT.
Eur. J. Comb., 2019

Polynomial size linear programs for problems in P.
Discret. Appl. Math., 2019

mplrs: A scalable parallel vertex/facet enumeration code.
Math. Program. Comput., 2018

On the ℋ-free extension complexity of the TSP.
Optim. Lett., 2017

An exponential lower bound for Cunningham's rule.
Math. Program., 2017

On the directed cut cone and polytope.
J. Comb. Optim., 2016

A parallel framework for reverse search using mts.
CoRR, 2016

On the extension complexity of combinatorial polytopes.
Math. Program., 2015

A generalization of extension complexity that captures P.
Inf. Process. Lett., 2015

George Dantzig: father of the simplex method.
Bull. EATCS, 2015

Comparative computational results for some vertex and facet enumeration codes.
CoRR, 2015

Ground metric learning.
J. Mach. Learn. Res., 2014

Reputation games for undirected graphs.
Discret. Appl. Math., 2014

Polynomial size linear programs for non-bipartite matching problems and other problems in P.
CoRR, 2014

Families of polytopal digraphs that do not satisfy the shelling property.
Comput. Geom., 2013

A Portable Parallel Implementation of the lrs Vertex Enumeration Code.
Proceedings of the Combinatorial Optimization and Applications, 2013

On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes.
Discret. Appl. Math., 2012

Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes
CoRR, 2011

Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Those ubiquitous cut polyhedra.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

From Bell Inequalities to Tsirelson's Theorem.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2009

Generating facets for the cut polytope of a graph by triangular elimination.
Math. Program., 2008

Computing monotone disjoint paths on polytopes.
J. Comb. Optim., 2008

Visualizing and Constructing Cycles in the Simplex Method.
Oper. Res., 2008

Enumerating Constrained Non-crossing Minimally Rigid Frameworks.
Discret. Comput. Geom., 2008

Multiparty Distributed Compression of Quantum Information.
Proceedings of the Second International Conference on Quantum, 2008

A list heuristic for vertex cover.
Oper. Res. Lett., 2007

Enumerating Non-crossing Minimally Rigid Frameworks.
Graphs Comb., 2007

Vašek Chvátal: A Very Short Introduction.
Graphs Comb., 2007

Graphs Comb., 2007

New classes of facets of the cut polytope and tightness of I<sub>mm22</sub> Bell inequalities.
Discret. Appl. Math., 2007

Distributed Compression and Multiparty Squashed Entanglement.
CoRR, 2007

Comparison of two bounds of the quantum correlation set.
Proceedings of the First International Conference on Quantum, Nano, and Micro Technologies, 2007

A Quantum Protocol to Win the Graph Colouring Game on All Hadamard Graphs.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2006

Un des "problèmes plaisans et délectables" de Claude Berge.
Discret. Math., 2006

On the fractional chromatic index of a graph and its complement.
Oper. Res. Lett., 2005

Solving Inequalities and Proving Farkas's Lemma Made Easy.
Am. Math. Mon., 2004

Stronger linear programming relaxations of max-cut.
Math. Program., 2003

On the chromatic polynomial of a graph.
Math. Program., 2002

On the Complexity of Testing Hypermetric, Negative Type, k-Gonal and Gap Inequalities.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

On the solitaire cone and its relationship to multi-commodity flows.
Math. Program., 2001

On the existence of a point subset with a specified number of interior points.
Discret. Math., 2001

On the binary solitaire cone.
Discret. Appl. Math., 2001

Estimating the number of vertices of a polyhedron.
Inf. Process. Lett., 2000

Two Conjectures on the Chromatic Polynomial.
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

Unoriented Theta-Maxima in the Plane: Complexity and Algorithms.
SIAM J. Comput., 1998

Proximity Constraints in Deformable Models for Cortical Surface Identification.
Proceedings of the Medical Image Computing and Computer-Assisted Intervention, 1998

On the Existence of a Point Subset with 4 or 5 Interior Points.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 1998

Living with <i>lrs</i>.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 1998

How Good Are Convex Hull Algorithms?.
Comput. Geom., 1997

Reverse Search for Enumeration.
Discret. Appl. Math., 1996

Generating Rooted Triangulations Without Repetitions.
Algorithmica, 1996

A Package for Triangulations.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

On the Sectional Area of Convex Polytopes.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Generating Rooted Triangulations with Minimum Degree Four.
Proceedings of the 8th Canadian Conference on Computational Geometry, 1996

Computational aspects of Helly's theorem and its relatives.
Int. J. Comput. Geom. Appl., 1995

How Good are Convex Hull Algorithms?
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Metric extensions and the L<sup>1</sup> hierarchy.
Discret. Math., 1994

Multiple surface identification and matching in magnetic resonance images.
Proceedings of the Visualization in Biomedical Computing 1994, 1994

The m-core properly contains the m-divisible points in space.
Pattern Recognit. Lett., 1993

A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra.
Discret. Comput. Geom., 1992

A Bound on the K-gonality of Facets of the Hypermetric Cone and Related Complexity Problems.
Comput. Geom., 1992

The cut cone, <i>L</i><sup>1</sup> embeddability, complexity, and multicommodity flows.
Networks, 1991

Distinct Distances Determined By Subsets of a Point Set in Space.
Comput. Geom., 1991

Locating a Robot with Angle Mathematics.
J. Symb. Comput., 1990

Algorithms for high dimensional stabbing problems.
Discret. Appl. Math., 1990

On the Complexity of Isometric Embedding in the Hypercube.
Proceedings of the Algorithms, 1990

On the Complexity of Single Fault Set Diagnosability and Diagnosis Problems.
IEEE Trans. Computers, 1989

Lower Bounds for Line Stabbing.
Inf. Process. Lett., 1989

All the Facets of the Six-point Hamming Cone.
Eur. J. Comb., 1989

Computing the volume of the union of spheres.
Vis. Comput., 1988

The Probabilistic Analysis of a Heuristic for the Assignment Problem.
SIAM J. Comput., 1988

Repeated distances in space.
Graphs Comb., 1988

Polyhedral Line transversals in Space.
Discret. Comput. Geom., 1988

A Generalized Theory for System Level Diagnosis.
IEEE Trans. Computers, 1987

Triangulating Point Sets in Space.
Discret. Comput. Geom., 1987

Algorithms for Line Transversals in Space.
Proceedings of the Third Annual Symposium on Computational Geometry, 1987

Visibility between two edges of a simple polygon.
Vis. Comput., 1986

diameter Partitioning.
Discret. Comput. Geom., 1986

Triangulating Simplicial Point Sets in Space.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

Eccentric graphs.
Discret. Math., 1985

Space Partitioning and its Application to Generalized Retrieval Problems.
Proceedings of the Foundations of Data Organization, 1985

Computing the largest empty convex subset of a set of points.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

On the partitionability of point sets in space (preliminary report).
Proceedings of the First Annual Symposium on Computational Geometry, 1985

Non-Partitionable Point Sets.
Inf. Process. Lett., 1984

A combinational approach to polygon similarity.
IEEE Trans. Inf. Theory, 1983

A survey of heuristics for the weighted matching problem.
Networks, 1983

Applications of a two-dimensional hidden-line algorithm to other geometric problems.
Computing, 1983

On a convex hull algorithm for polygons and its application to triangulation problems.
Pattern Recognit., 1982

An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge.
IEEE Trans. Computers, 1981

An efficient algorithm for decomposing a polygon into star-shaped polygons.
Pattern Recognit., 1981

A Linear Algorithm for Computing the Visibility Polygon from a Point.
J. Algorithms, 1981

Balancing signed graphs.
Discret. Appl. Math., 1981

Comments on a Lower Bound for Convex Hull Determination.
Inf. Process. Lett., 1980

On minimal 5-chromatic triangle-free graphs.
J. Graph Theory, 1979

A Linear Algorithm for Finding the Convex Hull of a Simple Polygon.
Inf. Process. Lett., 1979

An Omega(n^2 log n) Lower Bound to the Shortest Paths Problem
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977