Concept
Graphic matroid
Publications associées (16)
Entropic Matroids and Their Representation
This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw ...
2019Vector-Based 3D Graphic Statics: a framework for the design of spatial structures based on the relation between form and forces
Corentin Jean Dominique Fivet, Pierluigi D'Acunto
This article develops a vector-based 3D graphic statics framework that uses synthetic and intuitive graphical means for the analysis and design of spatial structures such as networks of bar elements in static equilibrium. It is intended to support the coll ...
2019On 2-Level Polytopes Arising In Combinatorial Settings
Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano
2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arisi ...
SIAM PUBLICATIONS2018Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
Nisheeth Vishnoi, Javad Ebrahimi Boroojeni, Damian Mateusz Straszak
Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the sim ...
Ieee2017CO2 emissions in relation to street-network configuration and city size
The street-network efficiency of tens of British cities in relation to transport fuel consumption and CO2 emissions are analyzed. The results show a strong linear positive correlation between length entropy and average street length, and a negative correla ...
Pergamon-Elsevier Science Ltd2015Order Types of Convex Bodies
We prove a Hadwiger transversal-type result, characterizing convex position on a family of non-crossing convex bodies in the plane. This theorem suggests a definition for the order type of a family of convex bodies, generalizing the usual definition of ord ...
2011Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approxima ...
Society for Industrial and Applied Mathematics2011Three-Sublattice Ordering of the SU(3) Heisenberg Model of Three-Flavor Fermions on the Square and Cubic Lattices
Frédéric Mila, Karlo Penc, Tamás András Tóth
Combining a semiclassical analysis with exact diagonalizations, we show that the ground state of the SU(3) Heisenberg model on the square lattice develops three-sublattice long-range order. This surprising pattern for a bipartite lattice with only nearest- ...
2010The Holt-Klee condition for oriented matroids
Holt and Klee have recently shown that every (generic) LP orientation of the graph of a d-polytope satisfies a directed version of the d-connectivity property, i.e. there are d internally disjoint directed paths from a unique source to a unique sink. We in ...
2009Finding Hamiltonian circuits in quasi-adjoint graphs
Dominique de Werra, Benjamin Leroy-Beaulieu
This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper pr ...
2008