Publications related to Lower Bounds on the Area Requirements of Series-Parallel Graphs

Related publications (18)

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Social-Transmotion: Promptable Human Trajectory Prediction

Alexandre Massoud Alahi, Saeed Saadatnejad, Yang Gao, Kaouther Messaoud Ben Amor

Accurate human trajectory prediction is crucial for applications such as autonomous vehicles, robotics, and surveillance systems. Yet, existing models often fail to fully leverage the non-verbal social cues human subconsciously communicate when navigating ...

2024

Rigidity-Aware Detection for 6D Object Pose Estimation

Mathieu Salzmann, Yinlin Hu

Most recent 6D object pose estimation methods first use object detection to obtain 2D bounding boxes before actually regressing the pose. However, the general object detection methods they use are ill-suited to handle cluttered scenes, thus producing poor ...

Ieee Computer Soc2023

Radatron: Accurate Detection Using Multi-resolution Cascaded MIMO Radar

Haitham Al Hassanieh, Junfeng Guan

Millimeter wave (mmWave) radars are becoming a more popular sensing modality in self-driving cars due to their favorable characteristics in adverse weather. Yet, they currently lack sufficient spatial resolution for semantic scene understanding. In this pa ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Pedestrian 3D Bounding Box Prediction

Alexandre Massoud Alahi, Saeed Saadatnejad, Yi Zhou Ju

Safety is still the main issue of autonomous driving, and in order to be globally deployed, they need to predict pedestrians' motions sufficiently in advance. While there is a lot of research on coarse-grained (human center prediction) and fine-grained pre ...

2022

Pedestrian Intention Prediction: A Multi-task Perspective

Alexandre Massoud Alahi, Saeed Saadatnejad

In order to be globally deployed, autonomous cars must guarantee the safety of pedestrians. This is the reason why forecasting pedestrians' intentions sufficiently in advance is one of the most critical and challenging tasks for autonomous vehicles. This w ...

2020

Improving Spatial Data Processing by Clipping Minimum Bounding Boxes

Anastasia Ailamaki, Eleni Tzirita Zacharatou, Darius Sidlauskas

The majority of spatial processing techniques rely heavily on the idea of approximating each group of spatial objects by their minimum bounding box (MBB). As each MBB is compact to store (requiring only two multi-dimensional points) and intersection tests ...

IEEE2018

3D Box Proposals from a Single Monocular Image of an Indoor Scene

Mathieu Salzmann

Modern object detection methods typically rely on bounding box proposals as input. While initially popularized in the 2D case, this idea has received increasing attention for 3D bounding boxes. Nevertheless, existing 3D box proposal techniques all assume h ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2018

A Framework for Collaborative Curation of Neuroscientific Literature

Sean Lewis Hill, Christian O'Reilly, Elisabetta Iavarone

Large models of complex neuronal circuits require specifying numerous parameters, with values that often need to be extracted from the literature, a tedious and error-prone process. To help establishing shareable curated corpora of annotations, we have dev ...

Frontiers Research Foundation2017

Boundary-aware Instance Segmentation

Mathieu Salzmann

We address the problem of instance-level semantic segmentation, which aims at jointly detecting, segmenting and classifying every individual object in an image. In this context, existing methods typically propose candidate objects, usually as bounding boxe ...

Ieee2017

Direct Prediction of 3D Body Poses from Motion Compensated Sequences

Pascal Fua, Vincent Lepetit, Artem Rozantsev, Bugra Tekin

We propose an efficient approach to exploiting motion information from consecutive frames of a video sequence to recover the 3D pose of people. Previous approaches typically compute candidate poses in individual frames and then link them in a post-processi ...

2016

Free Edge Lengths in Plane Graphs

Radoslav Fulek, Filip Moric

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a pla ...

Springer2015

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Bartosz Maria Walczak, Michal Lason

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...

Springer2014

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009

Graph-Based Approach for 3D Object Duplicate Detection

Touradj Ebrahimi, Frédéric Dufaux, Péter Vajda

In this paper, we consider the challenging problem of object duplicate detection and localization. Several applications require efficient object duplicate detection methods, such as automatic video and image tagging, video surveillance, and high level imag ...

2009

Pose Estimation for Category Specific Multiview Object Localization

Pascal Fua, Vincent Lepetit, Mustafa Özuysal

We propose an approach to overcome the two main challenges of 3D multiview object detection and localization: The variation of object features due to changes in the viewpoint and the variation in the size and aspect ratio of the object. Our approach procee ...

IEEE2009

Bicolored matchings in some classes of graphs

Dominique de Werra, Bernard Ries

We consider the problem of finding in a graph a set

R

of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with

n

nodes on each side, we give sufficient conditions f ...

2007

Efficient evaluation of piecewise control laws defined over a large number of polyhedra

Colin Neil Jones

We consider the class of piecewise state feedback control laws applied to discrete-time systems, motivated by recent work on the computation of closed-form MPC controllers. The on-line evaluation of such a control law requires the determination of the stat ...

2007