On transitive orientations of G-ê

Michael Andresen

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 3, page 423-467
  • ISSN: 2083-5892

Abstract

top
A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.

How to cite

top

Michael Andresen. "On transitive orientations of G-ê." Discussiones Mathematicae Graph Theory 29.3 (2009): 423-467. <http://eudml.org/doc/270909>.

@article{MichaelAndresen2009,
abstract = {A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.},
author = {Michael Andresen},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {comparability graph; edge deletion; transitive orientation; Triangle Lemma; Γ-components; open shop scheduling; irreducibility; triangle lemma; -components},
language = {eng},
number = {3},
pages = {423-467},
title = {On transitive orientations of G-ê},
url = {http://eudml.org/doc/270909},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Michael Andresen
TI - On transitive orientations of G-ê
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 423
EP - 467
AB - A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.
LA - eng
KW - comparability graph; edge deletion; transitive orientation; Triangle Lemma; Γ-components; open shop scheduling; irreducibility; triangle lemma; -components
UR - http://eudml.org/doc/270909
ER -

References

top
  1. [1] H. Bräsel, Lateinische Rechtecke und Maschinenbelegung (Habilitationsschrift. Technische Universität Otto-von-Guericke Magdeburg, 1990). 
  2. [2] H. Bräsel, Matrices in Shop Scheduling Problems, in: M. Morlock, C. Schwindt, N. Trautmann and J. Zimmermann, eds, Perspectives on Operations Research - Essays in Honor of Klaus Neumann (Gabler Edition Wissenschaft, Deutscher Universitätsverlag, 2006), 17-43. 
  3. [3] H. Bräsel, M. Harborth, T. Tautenhahn and P. Willenius, On the set of solutions of an open shop Problem, Ann. Oper. Res. 92 (1999) 241-263, doi: 10.1023/A:1018938915709. Zbl0958.90035
  4. [4] A. Cournier and M. Habib, A new linear algorithm for modular decomposition, in: S. Tison ed., Trees in Algebra and Programming, CAAP '94, 19th International Colloquium 787 of Lecture Notes in Computer Science (Springer Verlag, 1994) 68-82. 
  5. [5] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25-66, doi: 10.1007/BF02020961. 
  6. [6] P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964) 539-548, doi: 10.4153/CJM-1964-055-5. Zbl0121.26003
  7. [7] M.C. Golumbic, Comparability graphs and a new matroid, J. Combin. Theory (B) 22 (1977) 68-90, doi: 10.1016/0095-8956(77)90049-1. Zbl0352.05023
  8. [8] M.C. Golumbic, The complexity of comparability graph recognition and coloring, Comp. 18 (1977) 199-208, doi: 10.1007/BF02253207. Zbl0365.05025
  9. [9] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980). 
  10. [10] R.M. McConnell and J.P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, in: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms 5 (1994) 536-545. Zbl0867.05068
  11. [11] R.M. McConnell and J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999) 189-241, doi: 10.1016/S0012-365X(98)00319-7. Zbl0933.05146
  12. [12] R.M. McConnell and J.P. Spinrad, Ordered vertex partitioning, Discrete Math. and Theor. Comp. Sci. 4 (2000) 45-60. Zbl0946.68101
  13. [13] M. Moerig, Modulare Dekomposition durch geordnete Partitionierung der Knotenmenge: Grundlagen und Implementierung, (Diplomarbeit, Otto-von-Guericke-Universität Magdeburg, 2006). 
  14. [14] A. Natanzon, R. Shamir and R. Sharan, Complexity classification of some edge modification problems, Discrete Appl. Math. 113 (2001) 109-128, doi: 10.1016/S0166-218X(00)00391-7. Zbl0982.68104
  15. [15] K. Simon, Effiziente Algorithmen für perfekte Graphen (Teubner, 1992). 
  16. [16] P. Willenius, Irreduzibilitätstheorie bei Shop-Scheduling-Problemen (Dissertationsschrift, Shaker Verlag, 2000). 
  17. [17] M. Yannakakis, Edge deletion problems, SIAM J. Comput. 10 (2) (1981) 297-309, doi: 10.1137/0210021. Zbl0468.05043

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.