Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/13027Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Papadopoulos, C. | en |
| dc.contributor.author | Heggernes, P. | en |
| dc.contributor.author | Mancini, F. | en |
| dc.date.accessioned | 2015-11-24T17:25:20Z | - |
| dc.date.available | 2015-11-24T17:25:20Z | - |
| dc.identifier.issn | 0166-218X | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/13027 | - |
| dc.rights | Default Licence | - |
| dc.title | Minimal comparability completions of arbitrary graphs | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | 10.1016/j.dam.2007.08.039 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2008 | - |
| heal.abstract | A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes @P for which @P completion of arbitrary graphs can be achieved through such a vertex incremental approach. | en |
| heal.publisher | Elsevier | en |
| heal.journalName | Discrete Applied Mathematics | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Papadopoulos-2008-minimal comparability completions.pdf | 300.35 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
