Concept
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order. For any strict partially ordered set (S,
Official source
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.
Ontological neighbourhood
Related courses (2)
MATH-602: Inference on graphs
The class covers topics related to statistical inference and algorithms on graphs: basic random graphs concepts, thresholds, subgraph containment (planted clique), connectivity, broadcasting on trees,
CS-250: Algorithms I
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Related lectures (17)
Public Administration and Economic Measurement
Explores the impact of economic measurement choices on data visibility and governance, emphasizing the importance of defining categories for understanding and policymaking.
Partial Ordering: Relations, Sequences, Summation
Explores partial orderings, divisibility relations, lattices, lexicographic ordering, comparability, and total orderings.
Equivalence Relations and Partial Orderings
Introduces equivalence relations, partitions, partial orderings, and total ordering concepts with examples and definitions.
Related publications (30)
Graph-based approximate message passing iterations
Approximate message passing (AMP) algorithms have become an important element of high-dimensional statistical inference, mostly due to their adaptability and concentration properties, the state evolution (SE) equations. This is demonstrated by the growing ...
OXFORD UNIV PRESS2023Approximation Algorithms for Allocation and Network Design
In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...
EPFL2023Related people (6)