Another look at the degree constrained subgraph problem

DOI10.1016/0020-0190(81)90009-0zbMath0492.05041OpenAlexW2016856039MaRDI QIDQ1167739

Yossi Shiloach

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90009-0

zbMATH Keywords

matching problemconstrained subgraph problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (13)

Packings by Complete Bipartite Graphs ⋮ A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem ⋮ Degree-Constrained Subgraph Reconfiguration is in P ⋮ Influence of assortativity and degree-preserving rewiring on the spectra of networks ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Assigning papers to referees ⋮ A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs ⋮ Distributed backup placement in networks ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ Linear-time certifying algorithms for near-graphical sequences ⋮ Computing a consensus trajectory in a vehicular network

Cites Work

• Algorithms for edge coloring bipartite graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: Another look at the degree constrained subgraph problem