scientific article; zbMATH DE number 1420489

DOI<26::AID-NET3>3.0.CO;2-M 10.1002/(SICI)1097-0037(200001)35:1<26::AID-NET3>3.0.CO;2-MzbMath0938.90065MaRDI QIDQ4944739

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

Publication date: 27 June 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

complexityalgorithmsapproximationplanar graphstreewidthNP-completenessgraphsAT-free graphsinterval graphsasteroidal numbercomparability graphsdegree-preserving spanning tree

Mathematics Subject Classification ID

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

Related Items (9)

A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ On the directed full degree spanning tree problem ⋮ Unnamed Item ⋮ Spanning trees: A survey ⋮ Feedback vertex set on AT-free 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 ⋮ Spanning trees with disjoint dominating and 2-dominating sets ⋮ On the Directed Degree-Preserving Spanning Tree Problem

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth. Computations and approximations
• Independent sets in asteroidal triple-free graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: