Finding a sun in building-free graphs

DOI10.1007/s00373-011-1047-9zbMath1256.05082arXiv0910.1808OpenAlexW2147365795MaRDI 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)-freebuilding-freedistance hereditary

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

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