The Complexity of Finding Paths in Graphs with Bounded Independence Number

DOI10.1137/S0097539704441642MaRDI QIDQ5317191zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmscompletenessconnectivitydistance in graphsfirst-order definabilitylogarithmic spacepolynomial hierarchyreachabilityshortest pathssuccinct representationstournaments

Mathematics Subject Classification ID

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

Recommendations

• Counting independent sets in graphs with bounded bipartite pathwidth
• Counting independent sets in graphs with bounded bipartite pathwidth
• scientific article; zbMATH DE number 2090011
• An upper bound on the independence number of a graph computable in polynomial-time
• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number
• The complexity of some problems on maximal independent sets in graphs
• Algorithms for solving problems on graphs of bounded pathwidth
• Complexes of graphs with bounded independence number
• Complexes of graphs with bounded independence number
• On the independence polynomials of path-like graphs

Cited in

(9)

• A short note on the complexity of computing strong pathbreadth
• An upper bound on the independence number of a graph computable in polynomial-time
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• scientific article; zbMATH DE number 3876620 (Why is no real title available?)
• scientific article; zbMATH DE number 2090011 (Why is no real title available?)
• STACS 2004
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• On the parallel parameterized complexity of MaxSAT variants
• On the complexity of kings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317191)