The Minimum‐Cost Dynamic Flow Problem in a Fixed Graph With a Constant Target Flow Value Article Swipe
A dynamic network is a directed graph where an arc has a capacity and a transit time. A dynamic flow is a flow defined in a dynamic network. We consider the problem of finding a minimum‐cost dynamic flow in a dynamic network where an arc has a cost. It is known that this problem is NP‐hard. Klinz and Woeginger asked whether the minimum‐cost dynamic flow problem in a fixed graph (i.e., a graph is given a priori, and it is not a part of the input) can be solved in polynomial time. We prove that if the cost of each arc is non‐negative, the capacity of each arc is an integer, and the target flow value is a constant integer, then this problem can be solved in polynomial time.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1002/net.22272
- https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272
- OA Status
- bronze
- Cited By
- 1
- References
- 17
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4407938902
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4407938902Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1002/net.22272Digital Object Identifier
- Title
-
The Minimum‐Cost Dynamic Flow Problem in a Fixed Graph With a Constant Target Flow ValueWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-02-24Full publication date if available
- Authors
-
Naoyuki KamiyamaList of authors in order
- Landing page
-
https://doi.org/10.1002/net.22272Publisher landing page
- PDF URL
-
https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
bronzeOpen access status per OpenAlex
- OA URL
-
https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272Direct OA link when available
- Concepts
-
Constant (computer programming), Minimum-cost flow problem, Flow (mathematics), Multi-commodity flow problem, Graph, Mathematical optimization, Computer science, Mathematics, Value (mathematics), Flow network, Combinatorics, Geometry, Statistics, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1Per-year citation counts (last 5 years)
- References (count)
-
17Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4407938902 |
|---|---|
| doi | https://doi.org/10.1002/net.22272 |
| ids.doi | https://doi.org/10.1002/net.22272 |
| ids.openalex | https://openalex.org/W4407938902 |
| fwci | 5.01839543 |
| type | article |
| title | The Minimum‐Cost Dynamic Flow Problem in a Fixed Graph With a Constant Target Flow Value |
| awards[0].id | https://openalex.org/G2953040446 |
| awards[0].funder_id | https://openalex.org/F4320334764 |
| awards[0].display_name | |
| awards[0].funder_award_id | JP24K14825 |
| awards[0].funder_display_name | Japan Society for the Promotion of Science |
| biblio.issue | 4 |
| biblio.volume | 85 |
| biblio.last_page | 444 |
| biblio.first_page | 437 |
| topics[0].id | https://openalex.org/T10720 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9994999766349792 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Complexity and Algorithms in Graphs |
| topics[1].id | https://openalex.org/T12288 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9980999827384949 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Optimization and Search Problems |
| topics[2].id | https://openalex.org/T10996 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9916999936103821 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1704 |
| topics[2].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[2].display_name | Computational Geometry and Mesh Generation |
| funders[0].id | https://openalex.org/F4320334764 |
| funders[0].ror | https://ror.org/00hhkn466 |
| funders[0].display_name | Japan Society for the Promotion of Science |
| is_xpac | False |
| apc_list.value | 3400 |
| apc_list.currency | USD |
| apc_list.value_usd | 3400 |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2777027219 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6761860847473145 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1284190 |
| concepts[0].display_name | Constant (computer programming) |
| concepts[1].id | https://openalex.org/C99545648 |
| concepts[1].level | 3 |
| concepts[1].score | 0.6350646018981934 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q2897180 |
| concepts[1].display_name | Minimum-cost flow problem |
| concepts[2].id | https://openalex.org/C38349280 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5752313137054443 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1434290 |
| concepts[2].display_name | Flow (mathematics) |
| concepts[3].id | https://openalex.org/C170334043 |
| concepts[3].level | 3 |
| concepts[3].score | 0.5723035931587219 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q6934437 |
| concepts[3].display_name | Multi-commodity flow problem |
| concepts[4].id | https://openalex.org/C132525143 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5678343176841736 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[4].display_name | Graph |
| concepts[5].id | https://openalex.org/C126255220 |
| concepts[5].level | 1 |
| concepts[5].score | 0.5289160013198853 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[5].display_name | Mathematical optimization |
| concepts[6].id | https://openalex.org/C41008148 |
| concepts[6].level | 0 |
| concepts[6].score | 0.47013431787490845 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[6].display_name | Computer science |
| concepts[7].id | https://openalex.org/C33923547 |
| concepts[7].level | 0 |
| concepts[7].score | 0.45811834931373596 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[7].display_name | Mathematics |
| concepts[8].id | https://openalex.org/C2776291640 |
| concepts[8].level | 2 |
| concepts[8].score | 0.44222551584243774 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q2912517 |
| concepts[8].display_name | Value (mathematics) |
| concepts[9].id | https://openalex.org/C114809511 |
| concepts[9].level | 2 |
| concepts[9].score | 0.4104347825050354 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q1412924 |
| concepts[9].display_name | Flow network |
| concepts[10].id | https://openalex.org/C114614502 |
| concepts[10].level | 1 |
| concepts[10].score | 0.33978015184402466 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[10].display_name | Combinatorics |
| concepts[11].id | https://openalex.org/C2524010 |
| concepts[11].level | 1 |
| concepts[11].score | 0.07462504506111145 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[11].display_name | Geometry |
| concepts[12].id | https://openalex.org/C105795698 |
| concepts[12].level | 1 |
| concepts[12].score | 0.06500968337059021 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[12].display_name | Statistics |
| concepts[13].id | https://openalex.org/C199360897 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[13].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/constant |
| keywords[0].score | 0.6761860847473145 |
| keywords[0].display_name | Constant (computer programming) |
| keywords[1].id | https://openalex.org/keywords/minimum-cost-flow-problem |
| keywords[1].score | 0.6350646018981934 |
| keywords[1].display_name | Minimum-cost flow problem |
| keywords[2].id | https://openalex.org/keywords/flow |
| keywords[2].score | 0.5752313137054443 |
| keywords[2].display_name | Flow (mathematics) |
| keywords[3].id | https://openalex.org/keywords/multi-commodity-flow-problem |
| keywords[3].score | 0.5723035931587219 |
| keywords[3].display_name | Multi-commodity flow problem |
| keywords[4].id | https://openalex.org/keywords/graph |
| keywords[4].score | 0.5678343176841736 |
| keywords[4].display_name | Graph |
| keywords[5].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[5].score | 0.5289160013198853 |
| keywords[5].display_name | Mathematical optimization |
| keywords[6].id | https://openalex.org/keywords/computer-science |
| keywords[6].score | 0.47013431787490845 |
| keywords[6].display_name | Computer science |
| keywords[7].id | https://openalex.org/keywords/mathematics |
| keywords[7].score | 0.45811834931373596 |
| keywords[7].display_name | Mathematics |
| keywords[8].id | https://openalex.org/keywords/value |
| keywords[8].score | 0.44222551584243774 |
| keywords[8].display_name | Value (mathematics) |
| keywords[9].id | https://openalex.org/keywords/flow-network |
| keywords[9].score | 0.4104347825050354 |
| keywords[9].display_name | Flow network |
| keywords[10].id | https://openalex.org/keywords/combinatorics |
| keywords[10].score | 0.33978015184402466 |
| keywords[10].display_name | Combinatorics |
| keywords[11].id | https://openalex.org/keywords/geometry |
| keywords[11].score | 0.07462504506111145 |
| keywords[11].display_name | Geometry |
| keywords[12].id | https://openalex.org/keywords/statistics |
| keywords[12].score | 0.06500968337059021 |
| keywords[12].display_name | Statistics |
| language | en |
| locations[0].id | doi:10.1002/net.22272 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S191798613 |
| locations[0].source.issn | 0028-3045, 1097-0037 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | 0028-3045 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Networks |
| locations[0].source.host_organization | https://openalex.org/P4310320595 |
| locations[0].source.host_organization_name | Wiley |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310320595 |
| locations[0].source.host_organization_lineage_names | Wiley |
| locations[0].license | |
| locations[0].pdf_url | https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272 |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Networks |
| locations[0].landing_page_url | https://doi.org/10.1002/net.22272 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5004110613 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-7712-2730 |
| authorships[0].author.display_name | Naoyuki Kamiyama |
| authorships[0].countries | JP |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I135598925 |
| authorships[0].affiliations[0].raw_affiliation_string | Institute of Mathematics for Industry Kyushu University Fukuoka Japan |
| authorships[0].institutions[0].id | https://openalex.org/I135598925 |
| authorships[0].institutions[0].ror | https://ror.org/00p4k0j84 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I135598925 |
| authorships[0].institutions[0].country_code | JP |
| authorships[0].institutions[0].display_name | Kyushu University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Naoyuki Kamiyama |
| authorships[0].is_corresponding | True |
| authorships[0].raw_affiliation_strings | Institute of Mathematics for Industry Kyushu University Fukuoka Japan |
| has_content.pdf | True |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272 |
| open_access.oa_status | bronze |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Minimum‐Cost Dynamic Flow Problem in a Fixed Graph With a Constant Target Flow Value |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10720 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9994999766349792 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Complexity and Algorithms in Graphs |
| related_works | https://openalex.org/W3141113327, https://openalex.org/W3035974271, https://openalex.org/W2080904092, https://openalex.org/W4231500168, https://openalex.org/W3161514703, https://openalex.org/W2374451529, https://openalex.org/W2151525839, https://openalex.org/W2098682899, https://openalex.org/W1994440468, https://openalex.org/W2764325809 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1002/net.22272 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S191798613 |
| best_oa_location.source.issn | 0028-3045, 1097-0037 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | 0028-3045 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Networks |
| best_oa_location.source.host_organization | https://openalex.org/P4310320595 |
| best_oa_location.source.host_organization_name | Wiley |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310320595 |
| best_oa_location.source.host_organization_lineage_names | Wiley |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272 |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Networks |
| best_oa_location.landing_page_url | https://doi.org/10.1002/net.22272 |
| primary_location.id | doi:10.1002/net.22272 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S191798613 |
| primary_location.source.issn | 0028-3045, 1097-0037 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | 0028-3045 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Networks |
| primary_location.source.host_organization | https://openalex.org/P4310320595 |
| primary_location.source.host_organization_name | Wiley |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310320595 |
| primary_location.source.host_organization_lineage_names | Wiley |
| primary_location.license | |
| primary_location.pdf_url | https://onlinelibrary.wiley.com/doi/pdfdirect/10.1002/net.22272 |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Networks |
| primary_location.landing_page_url | https://doi.org/10.1002/net.22272 |
| publication_date | 2025-02-24 |
| publication_year | 2025 |
| referenced_works | https://openalex.org/W4211250771, https://openalex.org/W2076171427, https://openalex.org/W2234958105, https://openalex.org/W2170193147, https://openalex.org/W4229841241, https://openalex.org/W3194490636, https://openalex.org/W2972681478, https://openalex.org/W2898263215, https://openalex.org/W1968268863, https://openalex.org/W2566954515, https://openalex.org/W2066074485, https://openalex.org/W2008133042, https://openalex.org/W2114616381, https://openalex.org/W2096774592, https://openalex.org/W2401610261, https://openalex.org/W1490625391, https://openalex.org/W1977545325 |
| referenced_works_count | 17 |
| abstract_inverted_index.A | 1, 18 |
| abstract_inverted_index.a | 5, 12, 15, 22, 26, 35, 40, 47, 68, 72, 76, 82, 118 |
| abstract_inverted_index.It | 49 |
| abstract_inverted_index.We | 29, 93 |
| abstract_inverted_index.an | 9, 44, 110 |
| abstract_inverted_index.be | 88, 125 |
| abstract_inverted_index.if | 96 |
| abstract_inverted_index.in | 25, 39, 67, 90, 127 |
| abstract_inverted_index.is | 4, 21, 50, 55, 74, 80, 102, 109, 117 |
| abstract_inverted_index.it | 79 |
| abstract_inverted_index.of | 33, 84, 99, 106 |
| abstract_inverted_index.and | 14, 58, 78, 112 |
| abstract_inverted_index.arc | 10, 45, 101, 108 |
| abstract_inverted_index.can | 87, 124 |
| abstract_inverted_index.has | 11, 46 |
| abstract_inverted_index.not | 81 |
| abstract_inverted_index.the | 31, 62, 85, 97, 104, 113 |
| abstract_inverted_index.cost | 98 |
| abstract_inverted_index.each | 100, 107 |
| abstract_inverted_index.flow | 20, 23, 38, 65, 115 |
| abstract_inverted_index.part | 83 |
| abstract_inverted_index.that | 52, 95 |
| abstract_inverted_index.then | 121 |
| abstract_inverted_index.this | 53, 122 |
| abstract_inverted_index.Klinz | 57 |
| abstract_inverted_index.asked | 60 |
| abstract_inverted_index.cost. | 48 |
| abstract_inverted_index.fixed | 69 |
| abstract_inverted_index.given | 75 |
| abstract_inverted_index.graph | 7, 70, 73 |
| abstract_inverted_index.known | 51 |
| abstract_inverted_index.prove | 94 |
| abstract_inverted_index.time. | 17, 92, 129 |
| abstract_inverted_index.value | 116 |
| abstract_inverted_index.where | 8, 43 |
| abstract_inverted_index.(i.e., | 71 |
| abstract_inverted_index.input) | 86 |
| abstract_inverted_index.solved | 89, 126 |
| abstract_inverted_index.target | 114 |
| abstract_inverted_index.defined | 24 |
| abstract_inverted_index.dynamic | 2, 19, 27, 37, 41, 64 |
| abstract_inverted_index.finding | 34 |
| abstract_inverted_index.network | 3, 42 |
| abstract_inverted_index.priori, | 77 |
| abstract_inverted_index.problem | 32, 54, 66, 123 |
| abstract_inverted_index.transit | 16 |
| abstract_inverted_index.whether | 61 |
| abstract_inverted_index.ABSTRACT | 0 |
| abstract_inverted_index.capacity | 13, 105 |
| abstract_inverted_index.consider | 30 |
| abstract_inverted_index.constant | 119 |
| abstract_inverted_index.directed | 6 |
| abstract_inverted_index.integer, | 111, 120 |
| abstract_inverted_index.network. | 28 |
| abstract_inverted_index.Woeginger | 59 |
| abstract_inverted_index.NP‐hard. | 56 |
| abstract_inverted_index.polynomial | 91, 128 |
| abstract_inverted_index.minimum‐cost | 36, 63 |
| abstract_inverted_index.non‐negative, | 103 |
| cited_by_percentile_year.max | 95 |
| cited_by_percentile_year.min | 91 |
| corresponding_author_ids | https://openalex.org/A5004110613 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 1 |
| corresponding_institution_ids | https://openalex.org/I135598925 |
| citation_normalized_percentile.value | 0.85994921 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |