Elimination graphs
| Autor: | Allan Borodin, Yuli Ye |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Zdroj: | ACM Transactions on Algorithms. 8:1-23 |
| ISSN: | 1549-6333 1549-6325 |
| DOI: | 10.1145/2151171.2151177 |
| Popis: | In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = ( V, E ) with n vertices is said to have an inductive neighborhood property with respect to P if there is an ordering of vertices v 1 , …, v n such that the property P holds on the induced subgraph G [ N ( v i )∩ V i ], where N ( v i ) is the neighborhood of v i and V i = { v i , …, v n }. It turns out that if we take P as a graph with maximum independent set size no greater than k , then this definition gives a natural generalization of both chordal graphs and ( k + 1)-claw-free graphs. We refer to such graphs as inductive k -independent graphs. We study properties of such families of graphs, and we show that several natural classes of graphs are inductive k -independent for small k . In particular, any intersection graph of translates of a convex object in a two dimensional plane is an inductive 3 -independent graph; furthermore, any planar graph is an inductive 3 -independent graph. For any fixed constant k , we develop simple, polynomial time approximation algorithms for inductive k -independent graphs with respect to several well-studied NP-complete problems. Our generalized formulation unifies and extends several previously known results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|