Concept

Perfectly orderable graph

Related publications (7)

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and ...

2021

Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms

Maryam Kamgarpour, Tyler Summers, Baiwei Guo, Orcun Karaca

Actuator placement is an active field of research which has received significant attention for its applications in complex dynamical networks. In this paper, we study the problem of finding a set of actuator placements minimizing the metric that measures t ...

2020

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

Register allocation, in high-level synthesis and ASIP design, is the process of determining the number of registers to include in the resulting circuit or processor. The goal is to allocate the minimum number of registers such that no scalar variable is sp ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2007

Partitioning cographs into cliques and stable sets

Dominique de Werra, Tinaz Ekim

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case whe ...

2005

On randomized stopping points and perfect graphs

Dominique de Werra, Robert Dalang

Randomized stopping points form a convex set associated with the information structure that arises in the context of the optimal stopping problem for two-parameter processes. We study combinatorial properties of this structure when the underlying space is ...

Elsevier1988

Randomization in the two-parameter optimal stopping problem

Robert Dalang

The motivation to this research is the study of the optimal stopping problem for multiparameter processes : given a random process depending on finitely many parameters t = (t1,…,tn), which if stopped at point t in the parameter set produces a reward Xt, w ...

EPFL1987

On the average length of lexicographic paths

Thomas Liebling

A bound is given for the average length of a "lexicographic path", a definition that is motivated by degeneracies encountered when using the randomized simplex method. ...

1986

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.