Hardness Results and Efficient Algorithms for Graph Powers

DOI10.1007/978-3-642-11409-0_21zbMath1273.68150OpenAlexW1511737926MaRDI QIDQ5851109

Van Bang Le, Ngoc Tuy Nguyen

Publication date: 21 January 2010

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11409-0_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (6)

A unified approach to recognize squares of split graphs ⋮ A characterization of line graphs that are squares of graphs ⋮ Clustering powers of sparse graphs ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ Parameterized leaf power recognition via embedding into graph products

This page was built for publication: Hardness Results and Efficient Algorithms for Graph Powers