Minimum degree orderings

DOI10.1007/s00453-008-9239-2zbMath1187.68352OpenAlexW2170044697MaRDI QIDQ848936

Hiroshi Nagamochi

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9239-2

zbMATH Keywords

graph algorithmsedge-connectivitysubmodular functionsminimum cutsextreme subsetsmaximum adjacency orderingsminimum degree orderingsposi-modular functions

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Maximizing Symmetric Submodular Functions ⋮ Some Results about the Contractions and the Pendant Pairs of a Submodular System ⋮ Parsimonious formulations for low-diameter clusters ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Posimodular function optimization

Cites Work

• Unnamed Item
• A note on minimizing submodular functions
• Minimum cost subpartitions in graphs
• Edge-connectivity augmentation problems
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Minimizing symmetric submodular functions
• A correctness certificate for the Stoer-Wagner min-cut algorithm
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Minimum Cost Source Location Problems with Flow Requirements
• Smallest-last ordering and clustering and graph coloring algorithms
• Multi-Terminal Network Flows
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A new approach to the minimum cut problem
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• A simple min-cut algorithm
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
• Minimum cuts in near-linear time
• k-Components, Clusters and Slicings in Graphs
• Cutsets and partitions of hypergraphs

This page was built for publication: Minimum degree orderings