We study the problem of finding an acyclic orientation of an undirected graph G such that each path is contained in a limited number of maximal cliques of G. In general, in an acyclic oriented graph, each path is contained in more than one maximal cliques. We focus our attention on crown-free interval graphs, and show how to find an acyclic orientation of such a graph, which guarantees that each path is contained in at most four maximal cliques. The proposed technique is used to find approximated solutions for a class of related optimization problems where a solution corresponds to an acyclic orientation of graphs.
Confessore, G., Dell'Olmo, P., Giordani, S. (1999). Vertex Partitioning of Crown-Free Interval Graphs. ??????? it.cilea.surplus.oa.citation.tipologie.CitationProceedings.prensentedAt ??????? 25th International Workshop on Graph-Theoretic Concepts in Computer Science - WG'99, Ascona - Switzerland.
Vertex Partitioning of Crown-Free Interval Graphs
GIORDANI, STEFANO
1999-01-01
Abstract
We study the problem of finding an acyclic orientation of an undirected graph G such that each path is contained in a limited number of maximal cliques of G. In general, in an acyclic oriented graph, each path is contained in more than one maximal cliques. We focus our attention on crown-free interval graphs, and show how to find an acyclic orientation of such a graph, which guarantees that each path is contained in at most four maximal cliques. The proposed technique is used to find approximated solutions for a class of related optimization problems where a solution corresponds to an acyclic orientation of graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.