Distance-Hereditary Comparability Graphs |
| |
| Institution: | 1. MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing, China;2. Department of Civil and Environmental Engineering, National University of Singapore, Singapore;3. Centre for Maritime Studies, National University of Singapore, Singapore;1. Instituto Federal de Educação, Ciência e Tecnologia do Triângulo Mineiro, Brazil;2. Departamento de Administração Geral e Aplicada, Universidade Federal do Paraná, Brazil;3. Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA;1. LAMIH-UMR CNRS 8201, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont Houy, 59313 Valenciennes Cedex 9, France;2. Institut de Recherche Technologique Railenium, F-59300 Famars, France;1. EPF Lausanne, Switzerland;2. Rényi Institute Budapest, Hungary;3. ETH Zürich, Switzerland |
| |
| Abstract: | We study the class of the distance-hereditary comparability graphs, that is, those graphs which admit a transitive orientation and are completely decomposable with respect to the split decomposition. We provide a characterization in terms of forbidden subgraphs. We also provide further characterizations and one of them, based on the split decomposition, is used to devise a recognizing algorithm working in linear time. Finally, we show how to build distance-hereditary comparability graphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
