scientific article; zbMATH DE number 1420489

DOI10.1002/(SICI)1097-0037(200001)35:1%3C26::AID-NET3%3E3.0.CO;2-MMaRDI QIDQ4944739zbMATH OpenFDO

Authors Otto R. Koppius, Hilde Tuinstra, Andreas Huck, Ton Kloks, Dieter Kratsch, Haiko Müller, Hajo Broersma

Publication date 27 June 2000

Full work available at URL https://doi.org/10.1002/(SICI)1097-0037(200001)35:1%3C26::AID-NET3%3E3.0.CO;2-M

zbMATH Keywords

algorithmsapproximationasteroidal numberAT-free graphscomparability graphscomplexitydegree-preserving spanning treegraphsinterval graphsNP-completenessplanar graphstreewidth

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 1222606
• scientific article; zbMATH DE number 4112608
• scientific article; zbMATH DE number 4103101
• Degree conditions and degree bounded trees
• scientific article; zbMATH DE number 2044920
• Degree conditions for embedding trees
• Degrees of Souslin Trees
• Degree-preserving spanning trees in small-degree graphs
• Degree bounded spanning trees
• On the edge degrees of trees

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3803235 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• Independent sets in asteroidal triple-free graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth. Computations and approximations

Cited in

(16)

• Spanning trees with disjoint dominating and 2-dominating sets
• On degree preservable graphs
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• The degree-preserving spanning tree problem in strongly chordal and directed path graphs
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• On the directed degree-preserving spanning tree problem
• scientific article; zbMATH DE number 1222606 (Why is no real title available?)
• scientific article; zbMATH DE number 1305491 (Why is no real title available?)
• An infinite class of reach-preservable graphs
• Formulations and exact solution approaches for the degree preserving spanning tree problem
• On the directed full degree spanning tree problem
• scientific article; zbMATH DE number 1563034 (Why is no real title available?)
• Spanning trees: A survey
• Stable set reformulations for the degree preserving spanning tree problem
• Representing trees of higher degree
• Feedback vertex set on AT-free graphs

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 Q4944739)