Open Access
A Polynomial Algorithm for the k-cut Problem for Fixed k
Publication type: Journal Article
Publication date: 2008-10-31
scimago Q1
wos Q1
SJR: 1.349
CiteScore: 4.0
Impact factor: 1.9
ISSN: 0364765X, 15265471
Computer Science Applications
General Mathematics
Management Science and Operations Research
Abstract
The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in O(nk²/2−3k/2+4T(n, m)) steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.
Found
Nothing found, try to update filter.
Top-30
Journals
|
5
10
15
20
25
30
|
|
|
Lecture Notes in Computer Science
28 publications, 16.37%
|
|
|
Mathematical Programming
7 publications, 4.09%
|
|
|
Networks
7 publications, 4.09%
|
|
|
SIAM Journal on Discrete Mathematics
5 publications, 2.92%
|
|
|
Theoretical Computer Science
5 publications, 2.92%
|
|
|
Discrete Optimization
5 publications, 2.92%
|
|
|
Algorithmica
4 publications, 2.34%
|
|
|
Springer Optimization and Its Applications
4 publications, 2.34%
|
|
|
SIAM Journal on Computing
3 publications, 1.75%
|
|
|
Mathematics of Operations Research
3 publications, 1.75%
|
|
|
Journal of Combinatorial Optimization
3 publications, 1.75%
|
|
|
Information Processing Letters
3 publications, 1.75%
|
|
|
European Journal of Operational Research
3 publications, 1.75%
|
|
|
Operations Research Letters
2 publications, 1.17%
|
|
|
Journal of Parallel and Distributed Computing
2 publications, 1.17%
|
|
|
Discrete Applied Mathematics
2 publications, 1.17%
|
|
|
Algorithms
2 publications, 1.17%
|
|
|
Mathematical Programming Computation
2 publications, 1.17%
|
|
|
Discrete Mathematics
2 publications, 1.17%
|
|
|
IEEE Transactions on Control of Network Systems
2 publications, 1.17%
|
|
|
Electronic Journal of Combinatorics
2 publications, 1.17%
|
|
|
Mathematical and Computer Modelling
1 publication, 0.58%
|
|
|
Journal of Algorithms
1 publication, 0.58%
|
|
|
ACM Transactions on Computation Theory
1 publication, 0.58%
|
|
|
Journal of Mechanical Design, Transactions Of the ASME
1 publication, 0.58%
|
|
|
Electronic Notes in Theoretical Computer Science
1 publication, 0.58%
|
|
|
Circuit World
1 publication, 0.58%
|
|
|
Journal of Computational Biology
1 publication, 0.58%
|
|
|
INFORMS Journal on Computing
1 publication, 0.58%
|
|
|
5
10
15
20
25
30
|
Publishers
|
10
20
30
40
50
60
|
|
|
Springer Nature
55 publications, 32.16%
|
|
|
Institute of Electrical and Electronics Engineers (IEEE)
41 publications, 23.98%
|
|
|
Elsevier
34 publications, 19.88%
|
|
|
Wiley
11 publications, 6.43%
|
|
|
Society for Industrial and Applied Mathematics (SIAM)
8 publications, 4.68%
|
|
|
Association for Computing Machinery (ACM)
4 publications, 2.34%
|
|
|
Institute for Operations Research and the Management Sciences (INFORMS)
4 publications, 2.34%
|
|
|
MDPI
2 publications, 1.17%
|
|
|
Electronic Journal of Combinatorics
2 publications, 1.17%
|
|
|
ASME International
1 publication, 0.58%
|
|
|
Emerald
1 publication, 0.58%
|
|
|
Mary Ann Liebert
1 publication, 0.58%
|
|
|
SAGE
1 publication, 0.58%
|
|
|
American Chemical Society (ACS)
1 publication, 0.58%
|
|
|
Public Library of Science (PLoS)
1 publication, 0.58%
|
|
|
American Physical Society (APS)
1 publication, 0.58%
|
|
|
Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
1 publication, 0.58%
|
|
|
10
20
30
40
50
60
|
- We do not take into account publications without a DOI.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
171
Total citations:
171
Citations from 2024:
13
(7.6%)
Cite this
GOST |
RIS |
BibTex |
MLA
Cite this
GOST
Copy
Goldschmidt O., Hochbaum D. S. A Polynomial Algorithm for the k-cut Problem for Fixed k // Mathematics of Operations Research. 2008. Vol. 19. No. 1. pp. 24-37.
GOST all authors (up to 50)
Copy
Goldschmidt O., Hochbaum D. S. A Polynomial Algorithm for the k-cut Problem for Fixed k // Mathematics of Operations Research. 2008. Vol. 19. No. 1. pp. 24-37.
Cite this
RIS
Copy
TY - JOUR
DO - 10.1287/moor.19.1.24
UR - https://doi.org/10.1287/moor.19.1.24
TI - A Polynomial Algorithm for the k-cut Problem for Fixed k
T2 - Mathematics of Operations Research
AU - Goldschmidt, Olivier
AU - Hochbaum, Dorit S.
PY - 2008
DA - 2008/10/31
PB - Institute for Operations Research and the Management Sciences (INFORMS)
SP - 24-37
IS - 1
VL - 19
SN - 0364-765X
SN - 1526-5471
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2008_Goldschmidt,
author = {Olivier Goldschmidt and Dorit S. Hochbaum},
title = {A Polynomial Algorithm for the k-cut Problem for Fixed k},
journal = {Mathematics of Operations Research},
year = {2008},
volume = {19},
publisher = {Institute for Operations Research and the Management Sciences (INFORMS)},
month = {oct},
url = {https://doi.org/10.1287/moor.19.1.24},
number = {1},
pages = {24--37},
doi = {10.1287/moor.19.1.24}
}
Cite this
MLA
Copy
Goldschmidt, Olivier, and Dorit S. Hochbaum. “A Polynomial Algorithm for the k-cut Problem for Fixed k.” Mathematics of Operations Research, vol. 19, no. 1, Oct. 2008, pp. 24-37. https://doi.org/10.1287/moor.19.1.24.