Linear-time certifying algorithms for near-graphical sequences

DOI10.1016/J.DISC.2008.05.005MaRDI QIDQ1045061zbMATH OpenOpenAlexFDO

Authors Pavol Hell, David 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

(\(g,f)\)-factor\(f\)-factorcertifying algorithmdegree sequencegraph factorgraphical sequence

Mathematics Subject Classification ID

Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• Degree sequences of multigraphs
• On Erdös-Gallai and Havel-Hakimi algorithms
• Constructive proof of deficiency theorem of \((g,f)\)-factor
• Minimum vertex weighted deficiency of (g,f)-factors: A greedy algorithm

Cites work

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

Cited in

(10)

• Relaxed and approximate graph realizations
• Recognition of split-graphic sequences
• Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains
• Efficiently realizing interval sequences
• Exact sampling of graphs with prescribed degree correlations
• Temporal graph realization from fastest paths
• Graphic approximation of integer sequences
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Realizing temporal transportation trees
• Constructive proof of deficiency theorem of \((g,f)\)-factor

Describes a project that uses

Uses Software

• LEDA

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

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