Graph-Theoretic Concepts in Computer Science

DOI10.1007/b93953zbMath1255.68107MaRDI QIDQ5902514

Hoàng-Oanh Le, Feodor F. Dragan, Andreas Brandstädt, Van Bang Le, Ryuhei Uehara

Publication date: 12 January 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-completeness; tree spanner; chordal bipartite graph; interval bigraph; probe interval graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

05C75: Structural characterization of families of graphs

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

Related Items

The zoo of tree spanner problems