On Linear Time Minor Tests with Depth-First Search
DOI10.1006/JAGM.1993.1001zbMATH Open0764.68107OpenAlexW2066904980WikidataQ56639266 ScholiaQ56639266MaRDI QIDQ4033754FDOQ4033754
Authors: Hans L. Bodlaender 
Publication date: 16 May 1993
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1993.1001
Recommendations
- scientific article; zbMATH DE number 140499
- Fast minor testing in planar graphs
- Fast minor testing in planar graphs
- scientific article; zbMATH DE number 1264417
- Minimax trees in linear time with applications
- Minimax Trees in Linear Time with Applications
- An optimal tester for \(k\)-linear
- An optimal tester for \(k\)-Linear
- scientific article; zbMATH DE number 1875415
- An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
dynamic programmingcyclegraph minorspathgrid graphdepth- first searchcircus graphlinear time minor tests
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Cited In (46)
- The \(k\)-distinct language: parameterized automata constructions
- On the complexity of rainbow coloring problems
- A new algorithm for finding trees with many leaves
- Two edge-disjoint paths with length constraints
- Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
- An exact algorithm for the maximum leaf spanning tree problem
- A new algorithm for minimum spanning tree using depth-first-search in an undirected graph
- Algorithm for two disjoint long paths in 2-connected graphs
- Approximation and kernelization for chordal vertex deletion
- Approximating long cycle above Dirac's guarantee
- Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
- Safe sets in graphs: graph classes and structural parameters
- Safe sets in graphs: graph classes and structural parameters
- Faster deterministic parameterized algorithm for \(k\)-path
- Spotting trees with few leaves
- Finding monotone paths in edge-ordered graphs
- A partial k-arboretum of graphs with bounded treewidth
- Title not available (Why is that?)
- A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
- Parameterized and approximation algorithms for finding two disjoint matchings
- Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
- Nonempty intersection of longest paths in series-parallel graphs
- Detours in directed graphs
- Approximating the maximum clique minor and some subgraph homeomorphism problems
- On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves
- On the space and circuit complexity of parameterized problems: classes and completeness
- Methods for determining cycles of a specific length in undirected graphs with edge weights
- A Simple 2-Approximation for Maximum-Leaf Spanning Tree
- On interval routing schemes and treewidth
- Mineurs d'arbres avec racines
- Subexponential parameterized algorithms
- Narrow sieves for parameterized paths and packings
- Low polynomial exclusion of planar graph patterns
- Integer programming methods for solving binary interdiction games
- Finding two edge-disjoint paths with length constraints
- Going far from degeneracy
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Finding detours is fixed-parameter tractable
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- Algorithms for long paths in graphs
- Algorithm engineering for color-coding with applications to signaling pathway detection
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- Title not available (Why is that?)
- Minors in graphs of large \(\theta_r\)-girth
- Parameterized algorithms for list \(K\)-cycle
- On Interval Routing Schemes and treewidth
This page was built for publication: On Linear Time Minor Tests with Depth-First Search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4033754)
