The Complexity of Finding Paths in Graphs with Bounded Independence Number

Arfst Nickelsen, Till Tantau

Type: Article

Publication Date: 2005-01-01

Citations: 12

DOI: https://doi.org/10.1137/s0097539704441642

View Publication

Locations

SIAM Journal on Computing - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Deciding Reachability in a Directed Graph given its Path Decomposition	2024	Ronak Bhadra Raghunath Tewari
+	An upper bound on the independence number of a graph computable in polynomial-time	1995	Carlos J. Luz
+	Log-space Algorithms for Paths and Matchings in k-trees	2009	Bireswar Das Samir Datta Prajakta Nimbhorkar
+	Log-space Algorithms for Paths and Matchings in k-trees	2009	Bireswar Das Samir Datta Prajakta Nimbhorkar
+	On the Power of Unambiguity in Logspace	2010	A. Pavan Raghunath Tewari N. V. Vinodchandran
+	On the Power of Unambiguity in Logspace	2010	A. Pavan Raghunath Tewari N. V. Vinodchandran
+	Complexity results on <i>k</i>-independence in some graph products	2024	Márcia R. Cappelle Erika M. M. Coelho Otávio Mortosa Julliano R. Nascimento
+	The Complexity of Determining Paths of Length k.	1983	Burkhard Monien
+ PDF Chat	Hamiltonicity, Path Cover, and Independence Number: An FPT Perspective	2024	Fedor V. Fomin Petr A. Golovach Danil Sagunov Kirill Simonov
+	On graphs coverable by k shortest paths	2022	Maël Dumas Florent Foucaud Anthony Perez Ioan Todinca
+	Long Directed Detours: Reduction to $2$-Disjoint Paths	2023	Ashwin Jacob Michał Włodarczyk Meirav Zehavi
+	Arc-Disjoint Paths and Trees in 2-Regular Digraphs	2012	Jørgen Bang‐Jensen Sven Simonsen
+	Arc-Disjoint Paths and Trees in 2-Regular Digraphs	2012	Jørgen Bang‐Jensen Sven Simonsen
+	A lower bound on the independence number of a graph	1998	Jochen Harant
+	A Note on the Inapproximability of Induced Disjoint Paths	2017	Gaoxiu Dong Weidong Chen
+ PDF Chat	On the complexity of the Eulerian path problem for infinite graphs	2024	Nicanor Carrasco-Vargas Valentino Delle Rose Cristóbal Rojas
+	A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs	2021	Rajesh Chitnis
+	Finding Detours is Fixed-parameter Tractable	2016	Ivona Bezáková Radu Curticapean Holger Dell Fedor V. Fomin
+	The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable	2013	Marek Cygan Dániel Marx Marcin Pilipczuk Michał Pilipczuk
+	The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable	2013	Marek Cygan Dániel Marx Marcin Pilipczuk Michał Pilipczuk

Works That Cite This (4)

Action	Title	Year	Authors
+ PDF Chat	On the Parallel Parameterized Complexity of MaxSAT Variants	2023	Max Bannach Malte Skambath Till Tantau
+ PDF Chat	Open questions in the theory of semifeasible computation	2006	Piotr Faliszewski Lane A. Hemaspaandra
+	Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems	2016	Tomoyuki Yamakami
+ PDF Chat	The Complexity of Computing the Size of an Interval	2006	Lane A. Hemaspaandra Christopher M. Homan Sven Kosub Klaus W. Wagner

Works Cited by This (1)

Action	Title	Year	Authors
+	Generalized degree conditions for graphs with bounded independence number	1995	Ralph J. Faudree Ronald J. Gould Linda Lesniak Terri Lindquester