On some optimization problems on \(k\)-trees and partial \(k\)-trees

DOI10.1016/0166-218X(92)00122-3zbMath0804.90123WikidataQ126772600 ScholiaQ126772600MaRDI QIDQ1315461

Daniel Granot, Darko Skorin-Kapov

Publication date: 10 March 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(k\)-tree\(k\)-complete graphpath distance optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Paths and cycles (05C38)

Related Items (6)

Heuristics for the network design problem with connectivity requirements ⋮ Efficient algorithms for center problems in cactus networks ⋮ Efficient algorithms for centers and medians in interval and circular-arc graphs ⋮ Network construction/restoration problems: cycles and complexity ⋮ Backup 2-center on interval graphs ⋮ On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Separating subgraphs in k-trees: Cables and caterpillars
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Computation of the center and diameter of outerplanar graphs
• Algorithms finding tree-decompositions of graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• The most reliable series-parallel networks
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• Networks immune to isolated failures
• Partitioning trees: Matching, domination, and maximum diameter
• Networks immune to isolated line failures
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: On some optimization problems on \(k\)-trees and partial \(k\)-trees