Finding a sun in building-free graphs

DOI10.1007/s00373-011-1047-9zbMath1256.05082arXiv0910.1808MaRDI QIDQ1926049

Jeremy P. Spinrad, Elaine M. Eschen, Chính T. Hoàng, R. Sritharan

Publication date: 27 December 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.1808

zbMATH Keywords

recognition algorithm; (building, gem)-free; (building, sun)-free; building-free; distance hereditary

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C17: Perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding and counting given length cycles
• On rigid circuit graphs
• Completely separable graphs
• Characterizations of strongly chordal graphs
• Distance-hereditary graphs
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Doubly lexical ordering of dense 0--1 matrices
• An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs
• On the Complexity of Finding a Sun in a Graph
• On brittle graphs
• Three Partition Refinement Algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• Finding houses and holes in graphs