Publication

On randomized stopping points and perfect graphs

Dominique de Werra, Robert Dalang
1988
Journal Articles

Abstract

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 finite, in which case this convex set can be identified with a bounded polyhedron. Study of the extreme points of this polytope motivates the definition of an apparently new class of perfectly orderable graphs. Properties of this class of graphs are examined. For this setting, it is shown that under a classical hypothesis of the probabilistic model, the extremal elements of the set of randomized stopping points are precisely ordinary stopping points.

Official source

https://infoscience.epfl.ch/entities/publication/ee23a254-7888-4247-896b-d627dc7289e9

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

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.

Dominique de Werra, Robert Dalang
1988
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/ee23a254-7888-4247-896b-d627dc7289e9

About this result

Related concepts (32)

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices. The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Related publications (4)

On randomized stopping points and perfect graphs

Chat with Graph Search

CP violation in K → μ+μ− with and without time dependence through a tagged analysis

Call Graphs for Languages with Parametric Polymorphism

RACE: Towards Exploring the Design Dimensions of a Route Assisting and Communicating System for Elderly