Hierarchical vertex ordering

Sung Ho Woo; Sung Bong Yang

doi:10.1007/3-540-45832-8_29

Hierarchical vertex ordering

Sung Ho Woo, Sung Bong Yang

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The k-way graph partitioning problem has been solved well through vertex ordering and dynamic programming which splits a vertex order into k clusters [2,12]. In order to obtain “good clusters” in terms of the partitioning objective, tightly connected vertices in a given graph should be closely placed on the vertex order. In this paper we present a simple vertex ordering method called hierarchical vertex ordering (HVO). Given a weighted undirected graph, HVO generates a series of graphs through graph matching to construct a tree. A vertex order is then obtained by visiting each nonleaf node in the tree and by ordering its children properly. In the experiments, dynamic programming [2] is applied to the vertex orders generated by HVO as well as various vertex ordering methods [1,6,9,10,11] in order to solve the k-way graph partitioning problem. The solutions derived from the vertex orders are then comapred. Our experimental results show that HVO outperforms other methods for almost all cases in terms of the partitioning objective. HVO is also very simple and straightforward.

Original language	English
Title of host publication	Graph Transformation - 1st International Conference, ICGT 2002, Proceedings
Editors	Andrea Corradini, Hartmut Ehrig, Hans-Jörg Kreowski, Grzegorz Rozenberg
Publisher	Springer Verlag
Pages	393-401
Number of pages	9
ISBN (Electronic)	9783540443100
DOIs	https://doi.org/10.1007/3-540-45832-8_29
Publication status	Published - 2002
Event	1st International Conference on Graph Transformation, ICGT 2002 - Barcelona, Spain Duration: 2002 Oct 7 → 2002 Oct 12

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2505
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	1st International Conference on Graph Transformation, ICGT 2002
Country/Territory	Spain
City	Barcelona
Period	02/10/7 → 02/10/12

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-45832-8_29

Cite this

Woo, S. H., & Yang, S. B. (2002). Hierarchical vertex ordering. In A. Corradini, H. Ehrig, H-J. Kreowski, & G. Rozenberg (Eds.), Graph Transformation - 1st International Conference, ICGT 2002, Proceedings (pp. 393-401). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2505). Springer Verlag. https://doi.org/10.1007/3-540-45832-8_29

Woo, Sung Ho ; Yang, Sung Bong. / Hierarchical vertex ordering. Graph Transformation - 1st International Conference, ICGT 2002, Proceedings. editor / Andrea Corradini ; Hartmut Ehrig ; Hans-Jörg Kreowski ; Grzegorz Rozenberg. Springer Verlag, 2002. pp. 393-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{811462b1e7fb4482b7231a4aa606db78,

title = "Hierarchical vertex ordering",

abstract = "The k-way graph partitioning problem has been solved well through vertex ordering and dynamic programming which splits a vertex order into k clusters [2,12]. In order to obtain “good clusters” in terms of the partitioning objective, tightly connected vertices in a given graph should be closely placed on the vertex order. In this paper we present a simple vertex ordering method called hierarchical vertex ordering (HVO). Given a weighted undirected graph, HVO generates a series of graphs through graph matching to construct a tree. A vertex order is then obtained by visiting each nonleaf node in the tree and by ordering its children properly. In the experiments, dynamic programming [2] is applied to the vertex orders generated by HVO as well as various vertex ordering methods [1,6,9,10,11] in order to solve the k-way graph partitioning problem. The solutions derived from the vertex orders are then comapred. Our experimental results show that HVO outperforms other methods for almost all cases in terms of the partitioning objective. HVO is also very simple and straightforward.",

author = "Woo, {Sung Ho} and Yang, {Sung Bong}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 1st International Conference on Graph Transformation, ICGT 2002 ; Conference date: 07-10-2002 Through 12-10-2002",

year = "2002",

doi = "10.1007/3-540-45832-8_29",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "393--401",

editor = "Andrea Corradini and Hartmut Ehrig and Hans-J{\"o}rg Kreowski and Grzegorz Rozenberg",

booktitle = "Graph Transformation - 1st International Conference, ICGT 2002, Proceedings",

address = "Germany",

}

Woo, SH & Yang, SB 2002, Hierarchical vertex ordering. in A Corradini, H Ehrig, H-J Kreowski & G Rozenberg (eds), Graph Transformation - 1st International Conference, ICGT 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2505, Springer Verlag, pp. 393-401, 1st International Conference on Graph Transformation, ICGT 2002, Barcelona, Spain, 02/10/7. https://doi.org/10.1007/3-540-45832-8_29

Hierarchical vertex ordering. / Woo, Sung Ho; Yang, Sung Bong.
Graph Transformation - 1st International Conference, ICGT 2002, Proceedings. ed. / Andrea Corradini; Hartmut Ehrig; Hans-Jörg Kreowski; Grzegorz Rozenberg. Springer Verlag, 2002. p. 393-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2505).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Hierarchical vertex ordering

AU - Woo, Sung Ho

AU - Yang, Sung Bong

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - The k-way graph partitioning problem has been solved well through vertex ordering and dynamic programming which splits a vertex order into k clusters [2,12]. In order to obtain “good clusters” in terms of the partitioning objective, tightly connected vertices in a given graph should be closely placed on the vertex order. In this paper we present a simple vertex ordering method called hierarchical vertex ordering (HVO). Given a weighted undirected graph, HVO generates a series of graphs through graph matching to construct a tree. A vertex order is then obtained by visiting each nonleaf node in the tree and by ordering its children properly. In the experiments, dynamic programming [2] is applied to the vertex orders generated by HVO as well as various vertex ordering methods [1,6,9,10,11] in order to solve the k-way graph partitioning problem. The solutions derived from the vertex orders are then comapred. Our experimental results show that HVO outperforms other methods for almost all cases in terms of the partitioning objective. HVO is also very simple and straightforward.

AB - The k-way graph partitioning problem has been solved well through vertex ordering and dynamic programming which splits a vertex order into k clusters [2,12]. In order to obtain “good clusters” in terms of the partitioning objective, tightly connected vertices in a given graph should be closely placed on the vertex order. In this paper we present a simple vertex ordering method called hierarchical vertex ordering (HVO). Given a weighted undirected graph, HVO generates a series of graphs through graph matching to construct a tree. A vertex order is then obtained by visiting each nonleaf node in the tree and by ordering its children properly. In the experiments, dynamic programming [2] is applied to the vertex orders generated by HVO as well as various vertex ordering methods [1,6,9,10,11] in order to solve the k-way graph partitioning problem. The solutions derived from the vertex orders are then comapred. Our experimental results show that HVO outperforms other methods for almost all cases in terms of the partitioning objective. HVO is also very simple and straightforward.

UR - http://www.scopus.com/inward/record.url?scp=84937232482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937232482&partnerID=8YFLogxK

U2 - 10.1007/3-540-45832-8_29

DO - 10.1007/3-540-45832-8_29

M3 - Conference contribution

AN - SCOPUS:84937232482

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 393

EP - 401

BT - Graph Transformation - 1st International Conference, ICGT 2002, Proceedings

A2 - Corradini, Andrea

A2 - Ehrig, Hartmut

A2 - Kreowski, Hans-Jörg

A2 - Rozenberg, Grzegorz

PB - Springer Verlag

T2 - 1st International Conference on Graph Transformation, ICGT 2002

Y2 - 7 October 2002 through 12 October 2002

ER -

Woo SH, Yang SB. Hierarchical vertex ordering. In Corradini A, Ehrig H, Kreowski H-J, Rozenberg G, editors, Graph Transformation - 1st International Conference, ICGT 2002, Proceedings. Springer Verlag. 2002. p. 393-401. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45832-8_29

Hierarchical vertex ordering

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this