Spanning trees with few branch vertices in graphs of bounded neighborhood diversity

DOI10.1007/978-3-031-32733-9_22OpenAlexW4377971972MaRDI QIDQ6148080

Luisa Gargano, Adele A. Rescigno

Publication date: 11 January 2024

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-32733-9_22

zbMATH Keywords

spanning treeneighborhood diversityfixed Parameterized algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem
• Lower and upper bounds for the spanning tree with minimum branch vertices
• Optimal time data gathering in wireless networks with multidirectional antennas
• Complexity of conflict-free colorings of graphs
• Bounded-degree spanning tree problems: models and new algorithms
• Spanning trees with a bounded number of branch vertices in a claw-free graph
• Collision-free path coloring with application to minimum-delay gathering in sensor networks
• A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
• Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
• Decomposition methods based on articulation vertices for degree-dependent spanning tree problems
• Algorithmic meta-theorems for restrictions of treewidth
• Spanning spiders and light-splitting switches
• Upper bounds to the clique width of graphs
• Parameterized complexity of immunization in the threshold model
• Parameterized complexity of happy coloring problems
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• Approximating spanning trees with few branches
• Cutting-plane-based algorithms for two branch vertices related spanning tree problems
• An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices
• An edge-swap heuristic for generating spanning trees with minimum number of branch vertices
• Integer programming in parameterized complexity: five miniatures
• Parameterized Algorithms for Modular-Width
• Intractability of Clique-Width Parameterizations
• Gathering with Minimum Delay in Tree Sensor Networks
• Graph minors. II. Algorithmic aspects of tree-width
• Evangelism in social networks: Algorithms and complexity
• Iterated Type Partitions
• On structural parameterizations of star coloring

This page was built for publication: Spanning trees with few branch vertices in graphs of bounded neighborhood diversity