On Linear Time Minor Tests with Depth-First Search
DOI10.1006/JAGM.1993.1001zbMATH Open0764.68107OpenAlexW2066904980WikidataQ56639266 ScholiaQ56639266MaRDI QIDQ4033754FDOQ4033754
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
- 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
- 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
- Faster deterministic parameterized algorithm for \(k\)-path
- Finding monotone paths in edge-ordered graphs
- Finding Detours is Fixed-Parameter Tractable
- A partial k-arboretum of graphs with bounded treewidth
- Going Far from Degeneracy
- Title not available (Why is that?)
- 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
- Safe Sets in Graphs: Graph Classes and Structural Parameters
- Spotting Trees with Few Leaves
- Integer programming methods for solving binary interdiction games
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- Algorithms for long paths in graphs
- Approximation and Kernelization for Chordal Vertex Deletion
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Low Polynomial Exclusion of Planar Graph Patterns
- 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
- Title not available (Why is that?)
- Finding Two Edge-Disjoint Paths with Length Constraints
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)
