Publications related to Some combinatorial optimization problems in graphs with applications in telecommunications and tomography

Detecting nanoscale vibrations as signature of life

Giovanni Dietler, Sandor Kasas, Giovanni Longo, Francesco Simone Ruggeri, Petar Stupar

The existence of life in extreme conditions, in particular in extraterrestrial environments, is certainly one of the most intriguing scientific questions of our time. In this report, we demonstrate the use of an innovative nanoscale motion sensor in life-s ...

National Academy of Sciences2015

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Anastasios Kyrillidis

Certain optimization problems in communication systems, such as limited-feedback constant-envelope beamforming or noncoherent M-ary phase-shift keying (MPSK) sequence detection, result in the maximization of a fixed-rank positive semidefinite quadratic for ...

Institute of Electrical and Electronics Engineers2014

Homometric sets in trees

Radoslav Fulek, Slobodan Mitrovic

Let G = (V, E) denote a simple graph with vertex set V and edge set E. The profile of a vertex set V' subset of V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric if their profiles are the same ...

Academic Press Ltd- Elsevier Science Ltd2014

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodo ...

IEEE2014

Using Pareto optimality to explore the topology and dynamics of the human connectome

Jean-Philippe Thiran, Alessandra Griffa, Patric Hagmann, Olaf Sporns

Graph theory has provided a key mathematical framework to analyse the architecture of human brain networks. This architecture embodies an inherently complex relationship between connection topology, the spatial arrangement of network elements, and the resu ...

Royal Soc2014

A Branch-and-Price Algorithm to Solve the Integrated Berth Allocation and Yard Assignment Problem in Bulk Ports

Michel Bierlaire, Tomas Robenek, Nitish Umang

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem ...

Elsevier Science Bv2014

Exploring the Volumetric City. A Methodology for Investigating the Topology and Morphology of Surface and Subsurface Urban Spatial Networks

Michael Robert Doyle

The urban underground has historically been developed as a series of sporadic responses to surface land shortage or to hide unsightly urban activities (Parriaux et al 2004; 2010). The Deep City project at the École polytechnique fédérale de Lausanne in Swi ...

2014

On grids in topological graphs

János Pach

A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a t ...

Elsevier Science Bv2014

Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Relationships between entities in datasets are often of multiple nature, like geographical distance, social relationships, or common interests among people in a social network, for example. This information can naturally be modeled by a set of weighted and ...

Institute of Electrical and Electronics Engineers2014

Some combinatorial optimization problems in graphs with applications in telecommunications and tomography

Graph Chatbot

Chat with Graph Search

Detecting nanoscale vibrations as signature of life

Node-weighted network design and maximum sub-determinants

Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Homometric sets in trees

LP-Based Algorithms for Capacitated Facility Location

Using Pareto optimality to explore the topology and dynamics of the human connectome

A Branch-and-Price Algorithm to Solve the Integrated Berth Allocation and Yard Assignment Problem in Bulk Ports

Exploring the Volumetric City. A Methodology for Investigating the Topology and Morphology of Surface and Subsurface Urban Spatial Networks

On grids in topological graphs

Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds

Using Pareto optimality to explore the topology and dynamics of the human connectome

A Branch-and-Price Algorithm to Solve the Integrated Berth Allocation and Yard Assignment Problem in Bulk Ports

Detecting nanoscale vibrations as signature of life

Exploring the Volumetric City. A Methodology for Investigating the Topology and Morphology of Surface and Subsurface Urban Spatial Networks

Node-weighted network design and maximum sub-determinants

Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds

On grids in topological graphs

LP-Based Algorithms for Capacitated Facility Location

Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Homometric sets in trees