The Complexity of Finding Paths in Graphs with Bounded Independence Number

DOI10.1137/S0097539704441642zbMath1079.68077OpenAlexW1983784492MaRDI QIDQ5317191

Arfst Nickelsen, Till Tantau

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539704441642

zbMATH Keywords

reachabilitycompletenessdistance in graphsconnectivitytournamentsshortest pathsapproximation algorithmsfirst-order definabilitypolynomial hierarchylogarithmic spacesuccinct representations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Descriptive complexity and finite models (68Q19)

Related Items (2)

On the complexity of kings ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs

This page was built for publication: The Complexity of Finding Paths in Graphs with Bounded Independence Number