Approximation and Exact Algorithms for Special Cases of Connected f-Factors

DOI10.1007/978-3-319-20297-6_23zbMath1465.68216OpenAlexW2295747861MaRDI QIDQ3194728

N. S. Narayanaswamy, C. S. Rahul

Publication date: 20 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-20297-6_23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Signed and weighted graphs (05C22)

Related Items (2)

On the complexity landscape of connected \(f\)-factor problems ⋮ Approximation algorithms for connected graph factors of minimum weight

Cites Work

• Graph factors and factorization: 1985--2003: a survey
• The complexity of regular subgraph recognition
• General factors of graphs
• An Ore-type condition for the existence of \(k\)-factors in graphs
• Connected factors in graphs -- a survey
• Connected \([a,b\)-factors in \(K_{1,n}\)-free graphs containing an \([a,b]\)-factor]
• The Design of Approximation Algorithms
• Approximability of Connected Factors
• Note on Hamilton Circuits
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A New Applicable Proof of the Euler Circuit Theorem
• An algorithmic proof of Tutte's f-factor theorem
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Some Theorems on Abstract Graphs
• The Factors of Graphs
• A Short Proof of the Factor Theorem for Finite Graphs

This page was built for publication: Approximation and Exact Algorithms for Special Cases of Connected f-Factors