Combinatorial optimization and its applications in electrical engineering  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
42559
Type K
Principal investigator Recski, András
Title in Hungarian Kombinatorikus optimalizálás alkalmazásai a villamosságtanban
Title in English Combinatorial optimization and its applications in electrical engineering
Panel Informatics and Electrical Engineering
Department or equivalent Department of Computer Science and Information Theory (Budapest University of Technology and Economics)
Participants Fogaras, Dániel
Frank, András
Friedl, Katalin
Laborczi, Péter
Mann, Zoltán Ádám
Marx, Dániel
Nagy, Gyula
Orbán, András
Szeszlér, Dávid
Szkaliczki, Tibor
Tapolcai, János
Wettl, Ferenc
Starting date 2003-01-01
Closing date 2007-12-31
Funding (in million HUF) 7.805
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
A kombinatorikus optimalizálás eszközeit (gráf- és matroidelméleti algoritmusok, bonyolultságelméleti vizsgálatok) alkalmaztuk villamosságtani és informatikai problémák megoldására, így konkrétan -- a nagybonyolultságú integrált áramkörök 2- és 3-dimenziós huzalozási kérdéseire (csatorna- vagy 'switchbox'-huzalozás, minimális összhosszúságú/területű/térfogatú huzalozás); -- hardware és software komponenseket egyaránt tartalmazó rendszerek szintézisére; -- távközlési hálózatok megbízhatóságának, szolgáltatás-minőségének növelésére; -- közlekedési hálózatok informatikai szolgáltatásaira (pl. haladó járművek adatai alapján a hálózat topológiájának vizsgálata, optimális útvonal javaslása); -- az adaptív elosztott multimédia szerver fejlesztésére; -- web oldalakon hatékonyabb kereső programmok készítésére. Eközben tiszta matematikai és számítástudományi eredményekhez is jutottunk, így konkrétan -- a gráfelméletben (összefüggőséget növelő kiegészítések, Hamilton-körök, gráf-izomorfia); -- a matroidelméletben (gyenge és erős leképezések); -- a kvantumszámításokban (periódikus függvények, rejtett részcsoportok); -- a paraméteres bonyolultságelméletben (gráfok és hipergráfok színezése és listaszínezése); -- rúdszerkezetek és ''tensegrity'' szerkezetek merevségének elméletében.
Results in English
Methods of combinatorial optimization (algorithms for graphs and matroids, complexity considerations) were applied for various problems in electrical engineering and informatics, in particular -- for the detailed routing of 2- and 3-dimensional VLSI circuits (channel and switchbox routing, minimum length/area/volume routing); -- for hardware/software codesign; -- for improving the quality of service of telecommunication networks; -- for integrated traffic information services (e.g. map generation and route guidance from floating car data); -- for the developments of adaptive distributed multimedia servers; -- for designing more effective search algorithms in the web graph. During these studies we also obtained results in pure mathematics and in theoretical computer science as well, in particular -- in the theory of graphs (connectivity augmentations, Hamiltonian circuits, graph isomorphism); -- in the theory of matroids (strong and weak maps); -- in quantum computing (periodic functions, hidden subgroup properties); -- in parametrized complexity theory (colouring or list-colouring of graphs and hypergraphs); -- in the theory of rigidity of bar-and-joint and tensegrity frameworks.
Full text http://real.mtak.hu/669/
Decision
Yes





 

List of publications

  
Marx D: Parametrized coloring problems on chordal graphs, Theoretical Computer Science 351, 407-424, 2006
Jüttner A; Orbán A; Fiala Z: Two new algorithms for UMTS access network topology design, European Journal of Operations Research 164, 456-474, 2005
Goldschmidt B; Szkaliczki T; Böszörményi L: Placement of nodes in an adaptive distributed multimedia server, Proc. 10th Internat. Euro-Par Conf. Pisa: 2004. 776-783, 2004
Ho PH; Tapolcai J; Cinkler T: Segment shared protection in mesh communication networks with bandwidth guaranteed tunnels, IEEE/ACM Trans. on Networking, 12, 6, 1105-1118, 2004
Tapolcai J: Az optikai hálózatok jövője, Híradástechnika 2003. 46-49, 2003
Tapolcai J; Ho PH: Linear formulation for segment shared protection, Optical Networking and Communications, 2003. pp. 49-58, 2003
Arató P; Mann ÁZ; Orbán A: Time-constrained design of pipelined control-intensive systems, Periodica Polytechnica Ser. El. Eng. 48, 133-149, 2004
Frank A; Király T: Combined connectivity augmentation and orientation problems, Discrete Applied Math 131: 401-419, 2003
Frank A; Király T; Kriesell M: On decomposing a hypergraph into k connected sub-hypergraphs, Discrete Applied Math 131: 373-383, 2003
Fogaras D: Algorithms on the web graph, 3rd Hungarian-Japanese Symposium on Discrete Mathematics and its Applications, Tokyo, 240-249, 2003
Fogaras D: Where to start browsing the net?, 3rd Workshop on Innovative Internet Community Systems, Springer, 2003
Fogaras D: Ranking the pages of the World Wide Web, Per. Polytechnica 48: 5-10, 2004
Fogaras D; Rácz B: Towards scaling fully personalized page rank, 3rd Workshop on Algorithms and Models for the Web-Graph (WAW 2004), Springer, 2004
Fogaras D; Rácz B: A scalable randomized method to compute link-based similarity rank on the web graph, Clustering information over the web, Springer, 2004
Fogaras D; Rácz B: Scaling link based similarity search, Proc. 14th Internat. Conf. on the World Wide Web, Chiba, 641-650., 2005
Frank A: An algorithm to increase the node-connectivity of a digraph, 3rd Hungarian-Japanese Symposium on Discrete Mathematics and its Applications, Tokyo, 378-387, 2003
Frank A; Szegő L: Constructive characterizations for packing and covering with trees, Discrete Applied Math 131: 347-371, 2003
Frank A: Restricted t-matchings in bipartite graphs, Discrete Applied Math 131: 337-346, 2003
Frank A; Király T; Király Z: On the orientation of graphs and hypergraphs, Discrete Applied Math 131: 385-400, 2003
Arató P; Mann ZÁ; Orbán A: Algorithmic aspects of hardware-software partitioning, ACM Trans. on Design Automation of Electronic Systems 10: 136-156, 2005
Arató P; Mann ZÁ; Orbán A: Component-based hardware/software co-design, Proc. 17th Internat. Conf. on Architecture of Computing Systems, Augsburg: 2004. Springer, pp. 169-183, 2004
Marx D: List edge multicoloring in bounded cyclicity graphs, 3rd Hungarian-Japanese Symposium on Discrete Mathematics and its Applications, Tokyo: 2003. pp 164-170, 2003
Marx D: Eulerian disjoint path problem in grid graphs is NP-complete, Discrete Applied Math. 143: 336-341, 2004
Arató P; Mann ZÁ; Orbán A: Time-constrained scheduling of large pipelined datapaths, J. of Systems Architecture 51, 665-687, 2005
Friedl K: Periodic functions and quantum computing, 3rd Hungarian-Japanese Symposium on Discrete Mathematics and its Applications, Tokyo, 303-308, 2003
Friedl K; Magniez F; Sántha M; Sen P: Quantum testers for hidden group properties, 28th International Symposium on Mathematical Foundations of Computer Science, 419-428, 2003
Friedl K; Rónyai L: Order shattering and Wilson's theorem, Discrete Math 270: 126-135, 2003
Laborczi P: Efficient mapping algorithms for survivable GMPLS networks, Optical Networking and Communications, 174-184, 2003
Laborczi P; Zajicek J: How to generate a graph-based map from floating car data?, Proc. 10th World Congress on ITS, Madrid, no. 2737, 2003
Cinkler T; Laborczi P; Pióro M: Fairness considerations with algorithms for routing elasctic traffic, J of Telecommunications and Information Technology 2 3-12, 2004
Laborczi P; Cinkler T: Efficient algorithms for physically disjoint routing in survivable GMPLS/ASTN networks, Networks, Vienna: 2004. pp. 185-192, 2004
Laborczi P; Zajicek J; Reitmeier M: Generate and update maps as by-product of tracking vehicle fleets, Proc. 4th European Congress on ITS, Budapest: 2004 no. 2864, 2004
Laborczi P; Nowotny B; Linauer M; Schneider R; Karim R; Leihs D: Optimal route guidance based on floating car data, 10th World Conference on Transport Research, Istanbul: 2004. no. 225, 2004
Laborczi P; Leihs D; Linauer M; Nowotny B; Kispelyi B; Tomaschek T: Integrated traffic information services in Budapest and Vienna, 4th European Congress on ITS, Budapest, 24-26, 2004
Mann ZÁ; Orbán A: Optimization problems in system-level synthesis, 3rd Hungarian-Japanese Symposium on Discrete Mathematics and its Applications, Tokyo: 2003. 222-231, 2003
Mann ZÁ; Orbán A: Extending component-based design with hardware components, J. Science of Computer Programming 56, 23-39, 2005
Arató P; Juhász S; Mann ZÁ; Orbán A; Papp D: Hardware-software partitioning in embedded systems design, IEEE International Symposium on Intelligent Signal Processing, Budapest: 2003. pp. 197-202, 2003
Marx D: List edge multicoloring in graphs with few cycles, Information Processing letters 89: 85-90, 2004
Marx D: Graph coloring problems and their applications in scheduling, Periodica Polytechnica Ser. El. Eng. 48: 5-10, 2004
Marx D: Minimum sum multicoloring on the edges of trees, Theoretical Computer Science 361, 133-149, 2006
Recski A; Salamon G; Szeszlér D: Improving size-bounds for subcases of square-shaped switchbox routing, Periodica Polytechnica Ser. El. Eng. 48: 55-60, 2004
Ambrus Somogyi K; Recski A: On the complexity of the channel routing problem in the dogleg-free multilayer Manhattan model, Acta Polytechnica Hung. 1: 89-97, 2004
Recski A; Szeszlér D: The evolution of an idea - Gallai's algorithm, Bolyai Society Mathematical Studies 15, 317-328, 2006
Szeszlér D: A new algorithm for 2-layer Manhattan channel routing, 3rd Hungarian-Japanese Symposium on Discrete Mathematics and its Applications, Tokyo: 2003. pp. 179-185, 2003
Stacho L; Szeszlér D: On a generalization of Chvátal's condition giving new Hamiltonian degree sequences, Discrete Mathematics 292, 159-165, 2005
Szkaliczki T: Routing with minimum wire length in the Manhattan model is NP-complete, Periodica Polytechnica 46: 175-194, 2003
Szkaliczki T; Böszörményi L: Incremental placement of nodes in a large-scale adaptive distributed multimedia server, Proc. Internat. Conf. on Distributed and Parallel Systems, Budapest: 2004. 165-172, 2004
Fogaras D; Rácz B; Csalogany K.; Sarlos T.: Towards scaling fully personalized page rank algorithms, lower bounds and experiments, Internet Mathematics, 2 (3) 333-358, 2005
Fogaras D; Rácz B: Linear approximation algorithms and space lower bounds for the (S)im(R)ank similarity function on massive graphs, Proc. 4th Japanese-Hungarian Symp. Discrete Math. and Its Appl., Budapest, 55-63., 2005
Salamon G.: Spanning tree optimization problems with degree based objective functions, Proc. 4th Japanese-Hungarian Symp. Discrete Math. and Its Appl., Budapest, 309-315., 2005
Tapolcai J; Ho PH: Dynamic survivable routing for shared segment protection, Journal of Communications and Networks, kozlesre elfogadva, 2005
Ho PH; Xiaohong, J.; Horiguchi, S.;Tapolcai J: A novel network planning algorithm with fixed alternate routing for MPLS traffic engineering, Dynamics of Continuous, Discrete and Impulsive Systems, Ser. B. 13, 165-186, 2006
Szigeti J.; Tapolcai J; Retvari G.; Laposi L.; Cinkler T.: Utvonalkijeloles es forgalomelvezetes tobb tartomanyu kapcsolt optikai hálózatokban, Híradástechnika 2004. 42-49, 2004
Laborczi P; Linauer M; Zajicek J; Reitmeier M: Dynamic digital map generation from floating car data, 10th World Conference on Transport Research, Istanbul, 2004
Hutter O; Szkaliczki T; Goldschmidt B: Host recommendation in the adaptive distributed multimedia server, ERCIM News 62, 34-35, 2005
Prangl M; Hellwagner H; Spielvogel C; Bischof H; Szkaliczki T: Real time automatic metal extraction of medical X-ray images for contrast improvement, SPIE Symp. on Medical Imaging, San Diego, poster, accepted, 2006
Marx D: Parametrized graph separation problems, Theoretical Computer Science 351, 394-406, 2006
Marx D: Parametrized complexity of constraint satisfaction problems, Computational Complexity, 14, 153-183, 2005
Marx D: NP-completeness of list coloring and precoloring extension on the edges of planar graphs, Journal of Graph Theory 49, 313-324, 2005
Marx D: A short proof of the NP-completeness of minimum sum interval coloring, Operations Research Letters, 33, 382-384, 2005
Marx D: The complexity of chromatic strength and chromatic edge-strength, Computational Complexity, kozlesre elfogadva, 2005
Marx D: Precoloring extension on unit interval graphs, Discrete Applied Mathematics 154, 995-1002, 2006
Marx D: Minimum sum multicoloring on the edges of planar graphs and partial k-trees, 2nd Workshop on Approximation and Online Algorithms, Bergen, 9-22., 2005
Marx D: Efficient approximation schemes for geometric problems?, 13rd Annual European Symposium on Algorithms, 448-459, 2005
Marx D: The closest substring problem with small distances, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 63-72, 2005
Friedl K; Ivanyos G; Sántha M: Efficient testing of groups, 37th ACM Symposium on Theory of Computing, 157-166., 2005
Friedl K; Ivanyos G; Sántha M; Verhoeven Y: On the black-box complexity of Sperner's Lemma, 15th International Symposium on Foundamentals of Computation Theory, 247-257., 2005
Recski A: Maps of matroids with applications, Discrete Mathematics 303, 175-185, 2005
Recski A; Szabo J: On the generalization of the matroid parity problem, Graph Theory, Trends in Mathematics, Birkhauser 347-354., 2006
Recski A; Shai, O: One-dimensional synthesis of graphs as tensegrity frameworks, 4th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, 284-288., 2005
Golda B; Laczay B; Mann Z. A.; Megyeri Cs.; Recski A: Implementation of VLSI Routing Algorithms, Intelligent Systems at the Service of Mankind, UBooks, 349-360., 2004
Tapolcai J; Cinkler T: On-line routing algorithms with shared protection in WDM networks, 7th IFIP Working Conference on Optical Network Design and Modelling, 2003
Draga B; Recski A: A new worst-case lower bound for the width of single row routing in the unconstrained two-layer model, 6th International Symposium on Computational Intelligence, 172-176., 2005
Fogaras D; Rácz B: Practical algorithms and lower bounds for similarity search in massive graphs, IEEE Trans. on Knowledge and Data Engineering, 2006
T. Sarlos,; A. A. Benczur; K. Csalogany; Fogaras D; Rácz B: To randomize or not to randomize: Space optimal summaries for hyperlink analysis, 15th Internat. World Wide Web Conf. 297-306, 2006
Recski A; Szeszlér D: Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI, Discrete Applied Mathematics 155, 44-52, 2007
Nagy Gy:: Tessellation-like rod-joint frameworks, Annales Univ. Sci. Budapest, kozlesre elfogadva, 2006
Nagy G; Meszaros G:: Algorithms in the surface reconstruction, Annual News, Szent Istvan University Ybl Miklos Faculty of Building Science, pp. 21-26., 2005
Katona J; Nagy Gy:: Writing Scripts to Extend Import of CAD Softwares, Annual News, Szent Istvan University Ybl Miklos Faculty of Building Science, pp. 67-71., 2005
Friedl K; Ivanyos G; Sántha M; Verhoeven Y: Locally 2-dimensional Sperner problems complete for the polynomial parity argument classes, Proc. 6th Conference on Algorithms and Complexity, Springer Lecture Notes on Computer Science Vol. 3998, pp. 380-391., 2006
Salamon G; Wiener G:: On finding spanning trees with few widths, Information Processing Letter, submitted, 2007
Karpati P; Szkaliczki T; Böszörményi L: Abstracting and characterizing distributed VoD servers, Proc. of HUBUSKA 3rd Open Workshop, Klagenfurt, pp. 16-29, 2006
Szkaliczki T; Goldschmidt B; Böszörményi L: Algorithmic background of the host recommendation in the adaptive distributed multimedia server, Proc. of HUBUSKA 3rd Open Workshop, Klagenfurt, 2006
Prangl M; Szkaliczki T:: Quality and utility modelling for universal multimedia access (UMA), Proc. of HUBUSKA 4th Open Workshop, Varna, 2006
Prangl M; Szkaliczki T; H. Hellwagner:: A framework for utility based multimedia adaptation, IEEE Trans. Circuits and Systems for Video Technology, accepted, 2006
G. Varro; Friedl K; D. Varro: Adaptive graph pattern matching for model transformations using model-sensitive search plans, Electronic Notes in Theoretical Computer Science Vol. 152, pp. 191-205., 2006
J. Tapolcai; P. Choda; T. Cinkler; K. Wajda; A. Jajszczyk; D. Verchere: Quantification of resilience and quality of service, Proc. IEEE Internat. Conf. on Communications, 2006
P. Laborczi; T. Cinkler: On-line routing and bandwidth allocation for elastic traffic and for its restoration, 12th Internat. Telecommunications Network Strategy and Planning Symp. (NETWORKS 2006), New Delhi, 2006
P. Laborczi; A. Torok; L. Vajda; G. Gordos: Scatternet formation in high-rate wireless personal area networks by integer linear programming, 12th Internat. Telecommunications Network Strategy and Planning Symp. (NETWORKS 2006), New Delhi, 2006
A. Torok; L. Vajda; P. Laborczi; Z. Fulop; B. Barcsik: Building scatternets in high-rate multi-hop dynamic personal area networks, World Telecommunications Congress, Budapest, 2006
A. Torok; L. Vajda; P. Laborczi; Z. Fulop; A. Vidacs: Analysis of scatternet formation in high-rate multi-hop WPANs, 17th IEEE Int. Symp. on Personal, Indoor and Mobile Radio Communications, Helsinki, 2006



Back »