Minimum degree orderings
DOI10.1007/S00453-008-9239-2zbMATH Open1187.68352OpenAlexW2170044697MaRDI QIDQ848936FDOQ848936
Authors: 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
Recommendations
graph algorithmsedge-connectivitysubmodular functionsminimum cutsextreme subsetsmaximum adjacency orderingsminimum degree orderingsposi-modular functions
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)
Cites Work
- Smallest-last ordering and clustering and graph coloring algorithms
- Minimizing symmetric submodular functions
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- A note on minimizing submodular functions
- Multi-Terminal Network Flows
- A Fast Algorithm for Optimally Increasing the Edge Connectivity
- Augmenting Undirected Edge Connectivity in Õ(n2) Time
- k-Components, Clusters and Slicings in Graphs
- A new approach to the minimum cut problem
- Minimum Cost Source Location Problems with Flow Requirements
- A simple min-cut algorithm
- Minimum cuts in near-linear time
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Title not available (Why is that?)
- Edge-connectivity augmentation problems
- A correctness certificate for the Stoer-Wagner min-cut algorithm
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
- Cutsets and partitions of hypergraphs
- Minimum cost subpartitions in graphs
Cited In (7)
- Parsimonious formulations for low-diameter clusters
- On minimizing symmetric set functions
- Maximizing symmetric submodular functions
- Minimum Degree Orderings
- Some results about the contractions and the pendant pairs of a submodular system
- Posimodular function optimization
- Why is maximum clique often easy in practice?
This page was built for publication: Minimum degree orderings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848936)