𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Note on Quasi‐triangulated Graphs

✍ Scribed by Gorgos, Ion; Hoàng, Chính T.; Voloshin, Vitaly

Book ID
118198098
Publisher
Society for Industrial and Applied Mathematics
Year
2006
Tongue
English
Weight
107 KB
Volume
20
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Recognizing quasi-triangulated graphs
Recognizing quasi-triangulated graphs
✍ Jeremy P Spinrad 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 206 KB

This paper discusses a method for recognizing certain graph classes based on elimination schemes more e ciently. We reduce the time bound for recognizing quasi-triangulated graphs from O(n 3 ) to O(n 2:77 ), and perfect elimination bipartite and cop-win graphs from O(n 3 ) to O(n 3 =log n).

2-Role assignments on triangulated graph
2-Role assignments on triangulated graphs
✍ Li Sheng 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 267 KB

If G is a graph, a k-role assignment is a function mapping each vertex into a role, a positive integer 1; 2; : : : ; k, so that if x and y have the same role, then the sets of roles assigned to their neighbors are the same. A graph is called a triangulated graph if it contains no chord-less cycle of

On kernels in i-triangulated graphs
On kernels in i-triangulated graphs
✍ F Maffray 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 319 KB

A directed graph is said to be kernel-perfect if every induced subgraph possesses a kernel (independent, absorbing subset). A necessary condition for a graph to be kernel-perfect is that every complete subgraph C has an absorbing vertex (i.e., a successor of all vertices of C). In this work, we show