Publication

Pseudo-Boolean functions and stability of graphs

Dominique de Werra
1984

Abstract

In this Daper the concept of conflict graph associated with a pseudo-Boolean function is discussed; one exploits the fact that the problem of finding a stable set with maximum weight in a graph can be reduced to the maximisation of a pseudo-Boolean function and conversely. On these Boolean foundations a graph theoretical procedure is developed associating to any graph another one having a strictly smaller stability number. Fragmentary computational experience seems to show that this reduction may be applied efficiently in algorithms for obtaining the stability number of a graph.

Official source

https://infoscience.epfl.ch/entities/publication/8a523f43-6bf9-4789-b878-fa0a1d1a714f

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
1984

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/8a523f43-6bf9-4789-b878-fa0a1d1a714f

About this result

Related concepts (32)

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

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 (15)

Pseudo-Boolean functions and stability of graphs

Chat with Graph Search

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Occlusion Resilient 3D Human Pose Estimation

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models