scientific article; zbMATH DE number 910922

MaRDI QIDQ4886099zbMATH OpenFDO

Authors David Eppstein

Publication date 23 March 1997

zbMATH Keywords

diameterdynamic programming algorithmisomorphismsneighbourhood coverpathsplanar graphsubgraph isomorphismtree decompositiontree width

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Subgraph Isomorphism in Planar Graphs and Related Problems
• Planar subgraph isomorphism revisited
• Faster algorithms for finding and counting subgraphs
• Surface split decompositions and subgraph isomorphism in graphs on surfaces
• Graph minors. II. Algorithmic aspects of tree-width

Cited in

(30)

• On problems without polynomial kernels
• A layer-decomposition with degree method for subgraphs recognition problem.
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• Distance measures for embedded graphs
• Algorithms by layer-decomposition for the subgraph recognition problem with attributes
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Surface split decompositions and subgraph isomorphism in graphs on surfaces
• Planar subgraph isomorphism revisited
• Computing and Drawing Isomorphic Subgraphs
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• scientific article; zbMATH DE number 4049079 (Why is no real title available?)
• The density maximization problem in graphs
• scientific article; zbMATH DE number 1974109 (Why is no real title available?)
• Subgraph Isomorphism in Planar Graphs and Related Problems
• scientific article; zbMATH DE number 1759547 (Why is no real title available?)
• scientific article; zbMATH DE number 6146491 (Why is no real title available?)
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Approximation of minimum weight spanners for sparse graphs
• Guard games on graphs: keep the intruder out!
• On MAX-SAT with cardinality constraint
• On MAX-SAT with cardinality constraint
• Finding and counting given length cycles
• Structural validation of synthetic power distribution networks using the multiscale flat norm
• Precoloring extension in planar near-Eulerian-triangulations
• Precoloring extension in planar near-Eulerian-triangulations
• Precoloring extension in planar near-Eulerian-triangulations (extended abstract)
• On the negative cost girth problem in planar networks
• On low tree-depth decompositions

This page was built for publication:

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