Linear-time certifying algorithms for near-graphical sequences

DOI10.1016/j.disc.2008.05.005zbMath1185.05135OpenAlexW2095991286MaRDI QIDQ1045061

Pavol Hell, David G. Kirkpatrick

Publication date: 15 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.05.005

zbMATH Keywords

degree sequence\(f\)-factorcertifying algorithmgraph factor(\(g,f)\)-factorgraphical sequence

Mathematics Subject Classification ID

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) Vertex degrees (05C07)

Related Items (5)

Efficiently Realizing Interval Sequences ⋮ Exact sampling of graphs with prescribed degree correlations ⋮ Recognition of split-graphic sequences ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Relaxed and approximate graph realizations

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A theorem on flows in networks
• Matching theory
• Another look at the degree constrained subgraph problem
• Graph factors
• Parallel concepts in graph theory
• Simplified existence theorems for \((g,f)\)-factors
• A remark on the existence of finite graphs
• TWO THEOREMS IN GRAPH THEORY
• Matrices of zeros and ones
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• Software reliability via run-time result-checking
• Realizing Degree Sequences in Parallel
• An algorithmic proof of Tutte's f-factor theorem
• Subgraphs with prescribed valencies
• The Factorization of Linear Graphs
• Reguläre Faktoren von Graphen.
• The Factors of Graphs

This page was built for publication: Linear-time certifying algorithms for near-graphical sequences