scientific article; zbMATH DE number 910922

MaRDI QIDQ4886099zbMATHFDO

Authors David Eppstein

Publication date 23 March 1997

zbMATH Keywords

pathsdiameterdynamic programming algorithmplanar graphisomorphismssubgraph isomorphismtree decompositiontree widthneighbourhood cover

Mathematics Subject Classification ID

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

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

(26)

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

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)