On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
From MaRDI portal
Publication:3304140
DOI10.4230/LIPICS.STACS.2018.41zbMath1487.68130arXiv1710.04376OpenAlexW2963360194MaRDI QIDQ3304140
Naoto Ohsaka, Tomoaki Ogasawara, Yoichi Iwata
Publication date: 5 August 2020
Full work available at URL: https://arxiv.org/abs/1710.04376
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (12)
Eccentricity queries and beyond using hub labels ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ On parameterized complexity of binary networked public goods game ⋮ The power of linear-time data reduction for maximum matching ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width
Cites Work
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
- A linear-time algorithm for a special case of disjoint set union
- The k most vital arcs in the shortest path problem
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- Optimal node ranking of tree in linear time
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Ordered colourings
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Tree-depth, subgraph coloring and homomorphism bounds
- Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
- On the difficulty of some shortest path problems
- Replacement paths and k simple shortest paths in unweighted directed graphs
- Applications of a Planar Separator Theorem
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- Faster scaling algorithms for general graph matching problems
- Rankings of Graphs
- Reachability and Distance Queries via 2-Hop Labels
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- An O(nm) time algorithm for finding the min length directed cycle in a graph
- Paths, Trees, and Flowers
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
This page was built for publication: On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
