Vertices removal for feasibility of clustered spanning trees

DOI10.1016/J.DAM.2020.08.030MaRDI QIDQ2663996zbMATH OpenOpenAlexFDO

Authors Nili Guttmann-Beck, Roni Rozen, Michal Stern

Publication date 20 April 2021

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

Full work available at URL https://doi.org/10.1016/j.dam.2020.08.030

zbMATH Keywords

Clustered Spanning Tree problem ,removing vertices, layered graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Clustered spanning tree -- conditions for feasibility
• The clustering matroid and the optimal clustering tree
• On the minimum routing cost clustered tree problem
• The complete optimal stars-clustering-tree problem
• On the clustered Steiner tree problem

Cites work

• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• A Characterization of Soft Hypergraphs
• Approximation algorithms for not necessarily disjoint clustered TSP
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Clustered spanning tree -- conditions for feasibility
• Degrees of acyclicity for hypergraphs and relational database schemes
• scientific article; zbMATH DE number 3641484 (Why is no real title available?)
• scientific article; zbMATH DE number 1114466 (Why is no real title available?)
• Hypergraphes arbores
• Minimum tree supports for hypergraphs and low-concurrency Euler diagrams
• On the Consecutive-Retrieval Problem
• Path-based supports for hypergraphs
• Procedures for travelling salesman problems with additional constraints
• Restricted delivery problems on a network
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The clustering matroid and the optimal clustering tree
• The complete optimal stars-clustering-tree problem
• Topics in Intersection Graph Theory

Cited in

(5)

• Clustered spanning tree -- conditions for feasibility
• Achieving feasibility for clustered traveling salesman problems using PQ‐trees
• Decomposing the feasibility of clustered spanning tree by paths
• Insertion and removal lists gaining clustered subtrees
• On the complexity of community-aware network sparsification

This page was built for publication: Vertices removal for feasibility of clustered spanning trees

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