EveN, S, AND KARIV, O An O(n25) algor, thm for maximum matching m general graphs. Proc 16th IEEE Syrup on Foundations of Computer Science, Berkeley, Cahf, 1975, pp. 100-112.

Google Scholar

[7]

GAgEY, M R, JOHNSON, D S, AND STOCKMEYER, L Some slmphfied NP-complete graph problems. Theor, Comput Scl. 1 (1976), 237-267

Google Scholar

[8]

HADLOCK, F.O Fmdlng a maximum cut of a planar graph in polynomial ume SIAM J Comput. 4 (1975), 221-225

Google Scholar

[9]

HARARY, F Graph Theory Addison-Wesley, Readmg, Mass., 1969

Google Scholar

[10]

HOPCROFT, J E, AND TAILIAN, R.E Dividing a graph into tnconnected components. SlAM Z Compul. 2, 3 (1973), 135-158

Google Scholar

[11]

HEDETNIEMI, S T Hereditary properties of graphs J Combinatorial Theory B 14 (1973), 94-99

Google Scholar

[12]

K/KUr~O, T, YOSHIDA, N, AND KAKUDA, Y Dominating set m planar graphs, Tech. Rep AL79-9, Institute of Electronics and Communication Engmeers of Japan, Tokyo, Japan, 1979, pp. 21-30

Google Scholar

[13]

KIRKPATRICK, D G., AND HELL, P on the completeness of a generalized matching problem. Proc 10th ACM Symp on Theory of Computing, San Diego, Cahf, 1978, pp. 240--245

Crossref

Google Scholar

[14]

KR1SHNAMOORTIIY, M S, AND DEo, N.Node-deletion NP-complete problems SlAM J. Comput. 8, 4 (197_9), 619-625.

Google Scholar

[15]

LEWIS, JM On the complexity of the maximum subgraph problem. Proc 10th ACM Symp on Theory of Computing, San Diego, Cahf, 1978, pp 265-274.

Crossref

Google Scholar

[16]

MONMA, C L, AND SIDNEY, J B.Sequencing with series-parallel procedure constraints Tech Rep 347, School of Operations Research and Industrial Engineering, Cornell Umv, Ithaca, N.Y, 1979.

Google Scholar

[17]

MOORE, E F., AND SHANNON, C E Reliable orcmts using rehable relays, I-II J Frankhn 1nat 262, 3 (1956), 191, and 4 (1956), 281

Google Scholar

[18]

NlsrtlZliK1, T, A~D SAJTO, N Necessary and su~ctent condmon for a graph to be three-terminal series-parallel-cascade J Combinatorial Theory B 24, 3 (1978), 344-361

Google Scholar

[19]

NISHIZEKI, T, TAKAMIZAWA, K., AND SAITO, N.Algorithms for detecting series-parallel graphs and D-charts. Trans Inst Elect Commun. Eng Japan 59, 3 (1976), 259-260

Google Scholar

[20]

TOMIZAWA, N. On a speoahzauon sequence from general matrolds to ladder graphs with special emphasis on the characterization of ladder matroids. RAAG Research Notes, Third Series, 191, Research Assoc of Applied Geometry, Tokyo, Japan, 1973.

Google Scholar

[21]

VALDES, J., TARffAN, R E, AND LAWLER, E.L. The recognmon of series--parallel digraph. Proc I l th Ann ACM Symp on Theory of Computing, Atlanta, Ga, 1979, pp 1-12

Crossref

Google Scholar

[22]

WATANABE, T, AE, T, AND NAKAMURA, A.On the node cover problem of planar graphs Proc of 1979 hit Symp on Ctrcmts and Systems, Tokyo, Japan, 1979, pp. 78-81.

Google Scholar

[23]

YANNAKAKIS, M Node- and edge-deletion NP-complete problems Proc 10th ACM Syrup on Theory of Computing, San Diego, Cahf, 1978, pp 253-264

Crossref

Google Scholar

Cited By

View all

Lenz R(2025)Pipe merging for transient gas network optimization problemsApplied Mathematical Modelling10.1016/j.apm.2024.115660137(115660)Online publication date: Jan-2025
https://doi.org/10.1016/j.apm.2024.115660
Almathkour FMagnouche YMahjoub ATaktak R(2024)Design of survivable networks with low connectivity requirementsInternational Transactions in Operational Research10.1111/itor.1351132:2(918-960)Online publication date: 18-Jul-2024
https://doi.org/10.1111/itor.13511
Deshpande SBalakrishnan H(2024)Characterizing Flow Complexity in Transportation Networks Using Graph HomologyIEEE Control Systems Letters10.1109/LCSYS.2024.34135978(1625-1630)Online publication date: 2024
https://doi.org/10.1109/LCSYS.2024.3413597
Show More Cited By

Index Terms

Linear-time computability of combinatorial problems on series-parallel graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Nonempty intersection of longest paths in series-parallel graphs

In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai's question is positive for several well-known classes ...
The circular chromatic number of series-parallel graphs

In this article, we consider the circular chromatic number χ_c(G) of series-parallel graphs G. It is well known that series-parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series-parallel graph ...
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

A Hamiltonian path of a graph G is a simple path that contains each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path (resp. cycle) problem involves testing whether a Hamiltonian path ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 29, Issue 3

July 1982

302 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322326

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1982

Published in JACM Volume 29, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

257
Total Citations
View Citations
1,779
Total Downloads

Downloads (Last 12 months)141
Downloads (Last 6 weeks)12

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lenz R(2025)Pipe merging for transient gas network optimization problemsApplied Mathematical Modelling10.1016/j.apm.2024.115660137(115660)Online publication date: Jan-2025
https://doi.org/10.1016/j.apm.2024.115660
Almathkour FMagnouche YMahjoub ATaktak R(2024)Design of survivable networks with low connectivity requirementsInternational Transactions in Operational Research10.1111/itor.1351132:2(918-960)Online publication date: 18-Jul-2024
https://doi.org/10.1111/itor.13511
Deshpande SBalakrishnan H(2024)Characterizing Flow Complexity in Transportation Networks Using Graph HomologyIEEE Control Systems Letters10.1109/LCSYS.2024.34135978(1625-1630)Online publication date: 2024
https://doi.org/10.1109/LCSYS.2024.3413597
Ceresuela JChemisana DLópez N(2024)Computation and validation of the Expected Value of Power of Two Terminal Series–Parallel PV arraysSustainable Energy Technologies and Assessments10.1016/j.seta.2024.10398271(103982)Online publication date: Nov-2024
https://doi.org/10.1016/j.seta.2024.103982
Călinescu GWang X(2024)A (1/2+1/60)—Approximation algorithm for Maximum Weight Series-Parallel SubgraphDiscrete Applied Mathematics10.1016/j.dam.2023.09.019354(241-261)Online publication date: Sep-2024
https://doi.org/10.1016/j.dam.2023.09.019
Xi WLin WLin Y(2024)Packing 2- and 3-stars into cubic graphsApplied Mathematics and Computation10.1016/j.amc.2023.128287460(128287)Online publication date: Jan-2024
https://doi.org/10.1016/j.amc.2023.128287
Hao BMichini C(2024)The price of Anarchy in series-parallel network congestion gamesMathematical Programming: Series A and B10.1007/s10107-022-01803-w203:1-2(499-529)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10107-022-01803-w
Meng XHu XTian YDong GLambiotte RGao JHavlin S(2023)Percolation Theories for Quantum NetworksEntropy10.3390/e2511156425:11(1564)Online publication date: 20-Nov-2023
https://doi.org/10.3390/e25111564
Voblyi V(2023)On Asymptotic Enumeration of Labeled Series-Parallel $$k$$-Cyclic GraphsJournal of Applied and Industrial Mathematics10.1134/S199047892204024X16:4(853-859)Online publication date: 6-Mar-2023
https://doi.org/10.1134/S199047892204024X
Chin FTing HTsin YZhang Y(2023)A linear-time certifying algorithm for recognizing generalized series–parallel graphsDiscrete Applied Mathematics10.1016/j.dam.2022.10.005325(152-171)Online publication date: Jan-2023
https://doi.org/10.1016/j.dam.2022.10.005
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Nonempty intersection of longest paths in series-parallel graphs

The circular chromatic number of series-parallel graphs

Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations