Concept

Longest path problem

Related publications (115)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Simplicity in complex networks: a path-based centrality

Nikolaos Geroliminis, Leonardo Bellocchi

Understanding travel behaviour in transportation system is key challenge to calibrate and simulate the usage of urban mobility networks. We define in this work a path-based centrality based on the simplicity of the path between two locations in road networ ...

2020

Specular Manifold Sampling for Rendering High-Frequency Caustics and Glints

Wenzel Alban Jakob, Tizian Lucien Zeltner

Scattering from specular surfaces produces complex optical effects that are frequently encountered in realistic scenes: intricate caustics due to focused reflection, multiple refraction, and high-frequency glints from specular microstructure. Yet, despite ...

ASSOC COMPUTING MACHINERY2020

Learning Approach to Delineation of Curvilinear Structures in 2D and 3D Images

Agata Justyna Mosinska

Detection of curvilinear structures has long been of interest due to its wide range of applications. Large amounts of imaging data could be readily used in many fields, but it is practically not possible to analyze them manually. Hence, the need for automa ...

EPFL2019

Graph Reduction with Spectral and Cut Guarantees

Andreas Loukas

Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for g ...

MICROTOME PUBL2019

Extrapolating Paths with Graph Neural Networks

Andreas Loukas, Jean-Baptiste Francis Marie Juliette Cordonnier

We consider the problem of path inference: given a path prefix, i.e., a partially observed sequence of nodes in a graph, we want to predict which nodes are in the missing suffix. In particular, we focus on natural paths occurring as a by-product of the int ...

IJCAI, Inc.2019

Weighted Matchings via Unweighted Augmentations

Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...

ASSOC COMPUTING MACHINERY2019

On the Rainbow Turan number of paths

Abhishek Methuku

Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

rDAN: Toward robust demand-aware network designs

Andreas Loukas

We currently witness the emergence of interesting new network topologies optimized towards the traffic matrices they serve, such as demand-aware datacenter interconnects (eg, ProjecToR) and demand-aware peer-to-peer overlay networks (eg, SplayNets). This p ...

2018

Traffic Receipts for Network Transparency

Pavlos Nikolopoulos

Today's Internet is not transparent: when packets get lost or delayed, there is typically no information about where the problem occurred, hence no information about who is responsible. This results in Internet service providers (ISPs) offering service lev ...

EPFL2018

A Single-Phase, Proximal Path-Following Framework

Volkan Cevher, Quoc Tran Dinh, Anastasios Kyrillidis

We propose a new proximal path-following framework for a class of constrained convex problems. We consider settings where the nonlinear-and possibly nonsmooth-objective part is endowed with a proximity operator, and the constraint set is equipped with a se ...

INFORMS2018