4th Japanese-Hungarian Symposium

on Discrete Mathematics and Its Applications

  June 3-6, 2005 in Budapest, Hungary


Useful hints


    How to get to the city?

You find detailed information about this on the homepage of the institute: http://www.renyi.hu/come.html

    Conference Site

Rényi  Institute
(formerly: Mathematical Research Institute of  the Hungarian Academy of Sciences),
H-1053 Budapest, Reáltanoda utca 13/15.
Phone number (+36-1)-483 8302,
fax number   (+36-1)-483 8333.

Overhead projectors and projectors for PC are available at in the auditorium. You can also use the PC there with Linux or Windows.
The institute is equipped with WiFi network,  so if you bring your laptop you can use it. Otherwise we will set up an account for you that you can use with the terminals in the institute.



We tried to arrange accommodation for every participant who asked us to do so. If you have not got any confirmation about your arrangement, please contact us. 


Registration will take place at the Guest House of the EötvösUniversity (also called Hotel Peregrinus) on Thursday evening from  6.00 p.m. to 8.00 p.m. and Friday morning at the conference site between 8.00 a.m. and 9.00 a.m.


   Scientific program

Friday, June 03. Saturday, June 04. Sunday, June 05. Monday, June 06.
Takao Asano
Congestion Minimization Confluent Flow Problem: Experimental Evaluation of Algorithms
László Lovász
Node models and edge models
Satoru Fujishige
Submodularity and Polyhedra
Kazuo Murota
M-Convex Functions on Jump Systems: Generalization of Minsquare Factor Problem
Takehiro Ito
Algorithm for Partitioning Graphs of Bounded Tree-Width of Supply and Demand
Tamás Király
Orientations with parity and capacity constraints
Kiyohito Nagano
A Strongly Polynomial Algorithm for Line Search in Submodular Polyhedra
Zsolt Fekete
Source location with rigidity and tree packing requirements
Alpár Jüttner
On Resource Constrained Optimization Problems
Gyula Pap
Packing non-returning A-paths
Mariko Sakashita
Laminar Covering Problem
Tibor Jordan
Uniquely Localizable Networks with Few Anchors

coffee break
Hiroshi Nagamochi
A Deterministic Algorithm for Finding All Minimum k-Way Cuts
Takeshi Tokuyama
Approximation Algorithms for Computing a Highly Dense Subgraph
Norihide Tokushige
Intersecting families - uniform versus weighted
Satoru Iwata
Linking Systems and Matroid Pencils
Toshimasa Ishii
Bisecting a Four-Connected Graph with Three Resource Sets
Shin-ichi Nakayama
An O(n^3) Time Algorithm for Obtaining the Minimum Vertex Ranking Spanning Tree on Permutation Graphs
Gyula OH Katona
Improved YBLM for Sperner families
Bill Jackson
On the Rank Function of the 3-Dimensional Rigidity
Gábor Salamon
Spanning Tree Optimization Problems with Degree Based Objective Functions
Dieter Rautenbach
Dominating and Large Induced Trees in Regular Graphs
Gábor Wiener
Approximately Separating Systems
Márton Makai
Rigid graphs from edge-pairs

lunch break
Toshimasa Watanabe
Improving Performance Ratios by Repeatedly Executing Approximation Algorithms for Several Graph Connectivity Related Problems
Toshihide Ibaraki
Road to "Problem Solving Engines"
Ken-ichi Kawarabayashi
Algorithmic aspects of Hadwiger's Conjecture
Akihisa Tamura
A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments
Mihály Bárász
An Algorithm For Source Location In Directed Graphs
Kazuya Haraguchi
Compactness of Classifiers by Iterative Compositions of Features
Yoichi Hanatani
Hajós Calculus on Planar Graphs
Naonori Kakimura
Sign-Solvable Linear Programs
Zoltán Király
On well-balanced orientations
Zoltán Füredi
The distribution of the angles on the plane
Wael El Oraiby
Planar k-sets under insertion
Hiroshi Hirai
Greedy Fans: A geometric approach to dual greedy algorithms

coffee break
Takuro Fukunaga
Edge packing problem with edge capacity constraints
Shigeaki Harada
Online Allocation with Risk Information
Shinya Fujita
Degree Conditions and Disjoint Cycles in Graphs
Taizo Sadahiro
Circuit Switched Broadcastings and Digit Tilings on Torus Networks
Gábor Simonyi
On the local chromatic number of graphs
Attila Sharinoumi Sali
Color critical hypergraphs and forbidden configurations
Dániel Fogaras
Linear approximation algorithms and space lower bounds for the SimRank similarity function on massive graphs
Yoshio Okamoto
Counting the Independent Sets of a Chordal Graph in Linear Time
László Végh
Primal-dual approach for directed vertex connectivity augmentation and generalizations
Satoshi Takata
Chomp with Poison-Strewn Chocolates
Kiyoshi Yoshimoto
2-factors and hamilton cycles in line graphs
Katsuhisa Yamanaka
Coding Floorplans with Fewer Bits
Zsolt Patakfalvi
Line graphs of cubic graphs are normal
Hiroki Nakayama
Comparing the strengths of the non-realizability certificates for oriented matroids
Péter Sziklai
DNA-words and word posets
Masashi Kiyomi
Enumerating Labeled Chordal Graphs on Complete Graph
Péter Biró
Stable matching with incremental algorithms - The last one gets his best stable partner
Tsuyoshi Ito
New classes of facets of cut polytope and tightness of I_mm22 Bell inequalities
Jácint Szabó
Some results on the degree prescribed factor problem
Attila Reiss
3-dimensional Channel Routing
Masahiko Murakami
Fast Algorithms for Computing Jones Polynomials of Certain Links
Tadashi Sakuma
The Packing Clutter of the Positive Cocircuits of an Oriented Matroid Whose Rank is <= 4
András Telcs
Intersection of Random Walks on hierarchical structures

Júlia Pap
Total dual integrality of a description of the stable marriage polyhedron
Kazuyuki Amano
Tighter Bounds on the OBDD size of Integer Multiplication
Yoshinori Teshima
Enumeration of Triangles Configuration in Cube Cutting
Gergely Lukácsy
A Generic framework for plagiarism detection in programs
Florent Domenach
Cryptomorphisms of Closure Systems Axiomatization and Structures
András Recski
One-Dimensional Synthesis of Graphs as Tensegrity Frameworks

Welcome party
Rényi Institute

Rényi Institute


Here is the proceedings.


Social Events

We plan to have a welcome party on Friday evening and a conference banquet on Sunday evening. Both are free of charge for participants.

    How to go to the conference site?

Friday morning organisers will be available in the lobby of Hotel Peregrinus  to escort you to the conference site. It takes about 5-8 minutes walking. One group will leave at around 8.00 a.m. and another at around 8.30 a.m. The organizers will also escort the participants staying at the Guest House of the Education Ministry at Friday morning 8:00 a.m.
  There is a map here  indicating the locations.

  An other map with the closer neighbourhood of the Rényi Institute.

    Public transport in Budapest

The trams, subways and city buses operate with pre-purchased tickets. One ticket costs 160 HUF, at each transfer you have to validate a new ticket. You can buy tickets at ticket offices which usually can be found at the entrances of subway stations. Tickets must be validated upon boarding a tram or bus or upon entering the subway station. There are other types of tickets: daily, weekly. You can read about the details here.


In Hungary the local currency is the Hungarian Forint (HUF). The present exchange rate for one US dollar is about 195 Forints, one Yen is about 1.85 Forints. Major credit cards are accepted at several shops.

If you wish to place an international call from Hungary, dial 00, wait for a new dial tone and then start with country code etc. If someone wish to reach you in Hungary from abroad, the area code of Hungary is 36, followed by 1 for Budapest and then 7 more digits (for example, +36-1-2664911 for the Guest House (Hotel Peregrinus), or 36-1-3177166 for the fax machine at the conference site).

       In case of emergency, you can call

András Recski

Work: 463-2585
Home: 209-7341

or Gyula Y. Katona

Work: 463 3161
Home: 223 5015
Cell phone: 06 30 64 64 527

(If you call from outside of Budapest dial 06-1-xxx xxxx, outside of Hungary 36-1-xxx xxxx.)

                                On behalf of the Organizing Committee

Gyula Y. Katona and Andras Recski